COMPUTING CLOSEST POINTS FOR SEGMENTS.

We consider the proximity problem of computing for each of n line segments the closest point from a given set of n points in the plane. It generalizes Hopcroft's problem and the nearest foreign neighbors problem. We show that it can be solved in O(n[sup 4/3]2[sup O(log[sup *]n)]) time. For the case of disjoint segments we reduce the problem to two dynamic problems for maintenance of points with segment queries. We present two different algorithms with O(log² n) query and (amortized) update time. With this we solve the problem of computing the closest point to each of n disjoint line segments in O(n log² n) time improving the best previously known result by a factor of log n. We show that the nearest foreign neighbors and the Hausdorff distance for disjoint, colored segments can be computed in the same time. [ABSTRACT FROM AUTHOR]