A linear time algorithm for finding all farthest neighbors in a convex polygon

DOI10.1016/0020-0190(89)90103-8zbMath0676.68080OpenAlexW2083706317MaRDI QIDQ1123027

Dina Kravets, Alok Aggarwal

Publication date: 1989

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

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

zbMATH Keywords

convex polygoncomputational geometryfarthest neighborsmatrix searching

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computing methodologies and applications (68U99)

Related Items

Selection and sorting in totally monotone arrays ⋮ Computing farthest neighbors on a convex polytope. ⋮ Base station placement on boundary of a convex polygon ⋮ On the angle restricted nearest neighbor problem ⋮ An optimal algorithm with unknown time complexity for convex matrix searching ⋮ An efficient algorithm for the three-dimensional diameter problem ⋮ Farthest-point queries with geometric and combinatorial constraints ⋮ On computing the optimal bridge between two convex polygons.

Cites Work

• The symmetric all-furthest-neighbor problem
• Finding the convex hull of a simple polygon