Optimal time bounds for some proximity problems in the plane

DOI10.1016/0020-0190(92)90133-GzbMath0761.68093OpenAlexW2034144081MaRDI QIDQ1198024

Alok Aggarwal, Prabhakar Raghavan, Prasoon Tiwari, Herbert Edelsbrunner

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90133-g

zbMATH Keywords

polygonlower boundproximitypoint setsclosest pairinteger element uniqueness problem

Mathematics Subject Classification ID

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

Related Items

An optimal algorithm for computing visible nearest foreign neighbors among colored line segments ⋮ COMPUTING CLOSEST POINTS FOR SEGMENTS ⋮ Finding a shortest diagonal of a simple polygon in linear time ⋮ Spanning trees in multipartite geometric graphs ⋮ Expected computations on color spanning sets ⋮ On Some Proximity Problems of Colored Sets ⋮ Lower bounds for approximate polygon decomposition and minimum gap

Cites Work

• Generalized Delaunay triangulation for planar graphs
• Geometric applications of a matrix-searching algorithm
• A linear algorithm for finding the convex hull of a simple polygon
• The all nearest-neighbor problem for convex polygons
• Finding the convex hull of a simple polygon
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item