A note on the all nearest-neighbor problem for convex polygons

DOI10.1016/0020-0190(79)90021-8zbMath0399.68071OpenAlexW1977176150MaRDI QIDQ1254857

Chung-Chun Yang, Ta-Tsien Li

Publication date: 1979

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

Full work available at URL: https://doi.org/10.1016/0020-0190(79)90021-8

zbMATH Keywords

Nearest-Neighbor Problem for Convex Polygons

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Convex sets in (2) dimensions (including convex curves) (52A10) Discrete mathematics in relation to computer science (68R99)

Related Items

Selection and sorting in totally monotone arrays ⋮ On approximation behavior of the greedy triangulation for convex polygons ⋮ Tetrahedrizing point sets in three dimensions ⋮ Complexity, convexity, and unimodality ⋮ Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm ⋮ Optimal parallel algorithms for point-set and polygon problems ⋮ A note on the proof of a concurrent program ⋮ An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons ⋮ The symmetric all-furthest-neighbor problem

Cites Work

• The all nearest-neighbor problem for convex polygons
• A fast convex hull algorithm
• Determining the minimum-area encasing rectangle for an arbitrary closed curve