Intersection and Closest-Pair Problems for a Set of Planar Discs

DOI10.1137/0214034zbMath0564.68052OpenAlexW2054621199MaRDI QIDQ3678687

Micha Sharir

Publication date: 1985

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0214034

zbMATH Keywords

computational geometrynearest neighborintersection detectionEfficient algorithmsgeneralized Voronoi diagramarea calculation

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Related Items (32)

On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles ⋮ Planning a purely translational motion of a convex object in two- dimensional space using generalized Voronoi diagrams ⋮ An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments ⋮ Using geometry to solve the transportation problem in the plane ⋮ Minimum weight euclidean matching and weighted relative neighborhood graphs ⋮ A sweepline algorithm for Voronoi diagrams ⋮ EUCLIDEAN VORONOI DIAGRAM FOR CIRCLES IN A CIRCLE ⋮ AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗ ⋮ A survey of motion planning and related geometric algorithms ⋮ Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm ⋮ A plane-sweep algorithm for finding a closest pair among convex planar objects ⋮ An algorithmic framework for the single source shortest path problem with applications to disk graphs ⋮ Dynamic connectivity in disk graphs ⋮ Unnamed Item ⋮ An efficient algorithm for construction of the power diagram from the voronoi diagram in the plane ⋮ An axiomatic approach to Voronoi-diagrams in 3D ⋮ A convex hull algorithm for discs, and applications ⋮ Characterization of contour elements that generate abstract Voronoi diagrams ⋮ A dynamic sampling approach towards computing Voronoi diagram of a set of circles ⋮ Disk packing for the estimation of the size of a wire bundle ⋮ Voronoi diagram of a circle set from Voronoi diagram of a point set: I. Topology ⋮ Voronoi diagram of a circle set from Voronoi diagram of a point set: II. Geometry ⋮ A multi-dimensional shooting algorithm for the two-facility location-allocation problem with dense demand ⋮ Divide-and-conquer for Voronoi diagrams revisited ⋮ SKEW VORONOI DIAGRAMS ⋮ Near optimal minimal convex hulls of disks ⋮ Linear expected complexity for directional and multiplicative Voronoi diagrams ⋮ Robust Construction of the Additively-Weighted Voronoi Diagram via Topology-Oriented Incremental Algorithm ⋮ On the construction of abstract Voronoi diagrams ⋮ Storing the subdivision of a polyhedral surface ⋮ The predicates of the Apollonius diagram: algorithmic analysis and implementation ⋮ Topology-Oriented Incremental Algorithm for the Robust Construction of the Voronoi Diagrams of Disks

This page was built for publication: Intersection and Closest-Pair Problems for a Set of Planar Discs