A plane-sweep algorithm for finding a closest pair among convex planar objects

DOI10.1007/3-540-55210-3_186zbMath1493.68367OpenAlexW1586293707MaRDI QIDQ5096784

Frank Bartling, Klaus Hinrichs

Publication date: 18 August 2022

Published in: STACS 92 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/3-540-55210-3_186

zbMATH Keywords

computational geometryplane-sweep algorithmclosest-pair problem

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (2)

An optimal algorithm for computing visible nearest foreign neighbors among colored line segments ⋮ A plane-sweep algorithm for the all-nearest-neighbors problem for a set of convex planar objects

Cites Work

• Unnamed Item
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• A sweepline algorithm for Voronoi diagrams
• Optimal Algorithms for the Intersection and the Minimum Distance Problems Between Planar Polygons
• Intersection and Closest-Pair Problems for a Set of Planar Discs
• Computing the extreme distances between two convex polygons
• Two-Dimensional Voronoi Diagrams in the L _p -Metric

This page was built for publication: A plane-sweep algorithm for finding a closest pair among convex planar objects