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

DOI10.1137/0214034MaRDI QIDQ3678687zbMATH OpenOpenAlexFDO

Authors 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

area calculationcomputational geometryEfficient algorithmsgeneralized Voronoi diagramintersection detectionnearest neighbor

Mathematics Subject Classification ID

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

Recommendations

• A convex hull algorithm for discs, and applications
• Improved algorithms for discs and balls using power diagrams
• scientific article; zbMATH DE number 140459
• Intersection queries in sets of disks
• Publication:4934236

Cited in

(41)

• 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
• A sweepline algorithm for Voronoi diagrams
• A survey of motion planning and related geometric algorithms
• On the area of the intersection of disks in the plane
• Decomposing trimmed surfaces using the Voronoï diagram and a scan line algorithm
• An axiomatic approach to Voronoi-diagrams in 3D
• A convex hull algorithm for discs, and applications
• Intersection queries in sets of disks
• Disk packing for the estimation of the size of a wire bundle
• Storing the subdivision of a polyhedral surface
• Using geometry to solve the transportation problem in the plane
• Near optimal minimal convex hulls of disks
• A dynamic sampling approach towards computing Voronoi diagram of a set of circles
• The predicates of the Apollonius diagram: algorithmic analysis and implementation
• An efficient algorithm for construction of the power diagram from the voronoi diagram in the plane
• scientific article; zbMATH DE number 1696628 (Why is no real title available?)
• Robust construction of the additively-weighted Voronoi diagram via topology-oriented incremental algorithm
• Improved algorithms for discs and balls using power diagrams
• AN EFFICIENT PARALLEL ALGORITHM FOR THE ASSIGNMENT PROBLEM ON THE PLANE∗
• SKEW VORONOI DIAGRAMS
• Intersection queries in sets of disks
• Minimum weight euclidean matching and weighted relative neighborhood graphs
• A plane-sweep algorithm for finding a closest pair among convex planar objects
• Topology-oriented incremental algorithm for the robust construction of the Voronoi diagrams of disks
• EUCLIDEAN VORONOI DIAGRAM FOR CIRCLES IN A CIRCLE
• scientific article; zbMATH DE number 7651184 (Why is no real title available?)
• 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
• An algorithmic framework for the single source shortest path problem with applications to disk graphs
• Dynamic connectivity in disk graphs
• Linear expected complexity for directional and multiplicative Voronoi diagrams
• Characterization of contour elements that generate abstract Voronoi diagrams
• Solving semi-discrete optimal transport problems: star shapedeness and Newton's method
• A multi-dimensional shooting algorithm for the two-facility location-allocation problem with dense demand
• VOROPACK-D: real-time disk packing algorithm using Voronoi diagram
• An optimal algorithm for shortest paths in unweighted disk graphs
• On the construction of abstract Voronoi diagrams
• Seek distances in disks with two independent heads per surface
• Divide-and-conquer for Voronoi diagrams revisited

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3678687)