Back to Search
Start Over
COMPUTING CLOSEST POINTS FOR SEGMENTS.
- Source :
- International Journal of Computational Geometry & Applications; Oct2003, Vol. 13 Issue 5, p419-438, 20p
- Publication Year :
- 2003
-
Abstract
- 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]
- Subjects :
- PROXIMITY spaces
VORONOI polygons
ALGORITHMS
ALGEBRA
GEOMETRY
MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 02181959
- Volume :
- 13
- Issue :
- 5
- Database :
- Complementary Index
- Journal :
- International Journal of Computational Geometry & Applications
- Publication Type :
- Academic Journal
- Accession number :
- 11784185
- Full Text :
- https://doi.org/10.1142/S0218195903001268