Intersection and Closest-Pair Problems for a Set of Planar Discs
Author:
- Micha SharirMSMicha Sharir
- 1 May 1985
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 14 (2) , 448-468
Abstract
Efficient algorithms for detecting intersections and computing closest neighbors in a set of circular discs, are presented and analyzed. They adapt known techniques for solving these problems for sets of points or of line segments. The main portion of the paper contains the construction of a generalized Voronoi diagram for a set of n (possibly intersecting) circular discs in time $O(n\log ^2 n)$, and its applications.
Keywords
This publication has 8 references indexed in Scilit:
- Efficient Detection of Intersections among SpheresThe International Journal of Robotics Research, 1983
- On the “piano movers'” problem I. The case of a two‐dimensional rigid polygonal body moving amidst polygonal barriersCommunications on Pure and Applied Mathematics, 1983
- Optimal Search in Planar SubdivisionsSIAM Journal on Computing, 1983
- Plane-sweep algorithms for intersecting geometric figuresCommunications of the ACM, 1982
- A New Approach to Planar Point LocationSIAM Journal on Computing, 1981
- Generalization of Voronoi Diagrams in the PlaneSIAM Journal on Computing, 1981
- Efficient computation of continuous skeletons1979
- Algorithms for Reporting and Counting Geometric IntersectionsIEEE Transactions on Computers, 1979