CERC 2010: Solutions' sketches
27.11.2010
A: ArdeniaIn this task, you are to compute a distance between two segments in three dimensional space. Let P_{0} and P_{1} be the endpoints of the first segment and Q_{0} and Q_{1} be the endpoints of the second one. Start by finding linear functions P and Q, such that P(0) = P_{0}, P(1) = P_{1}, Q(0) = Q_{0}, and Q(1) = Q_{1}. We also use P and Q for denoting segments and use p and q for the corresponding vectors, i.e., p = P(1)  P(0) and q = Q(1)  Q(0). First, we need a geometric primitives for computing the distance between a point A and a segment P. Observe that the distance is the minimum of the function d(P(x),A), where d is the distance between two points and x is from range [0,1]. Programming this primitive boils down to a simple function minimization. As a matter of fact, we may extend this approach to solve the actual problem: we have to find the minimum of d(P(x), Q(y)), where x and y are both from [0,1]. This can be also computed using calculus (slightly more involved than in the previous case). Below we present more algebraic approach (whose advantage is that it works also in higher dimensions). First, we check whether the segments are parallel. If so, the task reduces to finding the pointstosegment distances and checking some boundary cases. Otherwise, for nonparallel segments, we will find the pair of the closest points P(x), Q(y), where x and y are arbitrary real numbers. We use the fact that the for nonparallel segments, these points are unique and segment (P(x),Q(y)) is perpendicular both to P and to Q. By writing this segment as a vector w = P(x)  Q(y), we obtain that w · p = 0 and w · q = 0. This gives us two equations with two variables, x and y. After having computed x and y, it is sufficient to check whether P(x) and Q(y) lie in segments P and Q (i.e., whether x and y belong to [0,1]) or outside of them. In the latter case, the distance is minimized at some endpoint. B: BeastsBoundary of the upper (lower) gray region is called the upper (lower) envelope of a given set of lines. In the problem you are asked to find the distance between these two envelopes. Let's start with finding the envelopes themselves. As the situation is clearly symmetric, we can focus on finding the upper envelope, represented as a sequence of segments, with the leftmost and the rightmost segments halfinfinite. Start with transforming all equations into the form y=Ax+B, and observe that if one traverses the envelope from left to right, the encountered segments belong to lines with (strictly) increasing A coefficients. This suggest that we might try to sort the lines according to these coefficients and add them onebyone, updating the current envelope. We start with the envelope of the first two lines computed naively. Then, adding a line whose A coefficient is larger than the coefficient of all already processed lines requires:
These steps are illustrated on the following picture.
Assuming the segments are kept in a lefttoright sorted list, all these operations can be performed in constant time. We only need a few geometric primitives: checking if a point lies on the right side of a line, and computing the intersection of two lines (which you probably have already prewritten). Now the problem reduces to finding the distance between two sets of segments. It is not difficult to see that the smallest distance is achieved for a pair of points p,q such that either p or q is an endpoint of some segment. So, for each endpoint of the upper (lower) envelope segment we should find the closest point on the lower (upper) envelope. The envelopes can be thought of as convex polygons so you might use a generic distancetoconvexpolygon procedure. Here the situation is slightly less involved, though, and you can use a single binary search. Alternatively, you can observe that moving from lefttoright on one envelope results in moving the optimal point on the other one from lefttoright as well, and get a linear time for this part of the problem. The total complexity is O(n log n) because we need to sort the lines according to their angles.

Copyright © 20082010 Wrocławski Portal Informatyczny
design: rafalpolito.com