COMPUTING CLOSEST POINTS FOR SEGMENTS
Sergei N. Bespamyatnikh · International Journal of Computational Geometry & Applications · 2003
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 problem11 and the nearest foreign neighbors problem.15 We show that it can be solved in O(n4/32O( log * 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 2 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 2 n) time improving the best previously known result4 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.