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

DOI10.1016/0020-0190(89)90103-8MaRDI QIDQ1123027zbMATH OpenOpenAlexFDO

Authors 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

computational geometryconvex polygonfarthest neighborsmatrix searching

Mathematics Subject Classification ID

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

Review text

A linear-time algorithm is given to compute all most distant vertices for every vertex of a convex polygon. It is an extension of an algorithm from \textit{A. Aggarwal}, \textit{M. M. Klawe}, \textit{S. Moran}, \textit{P. Shor}, \textit{R. Wilber} [Algorithmica 2, 195-208 (1987; Zbl 0642.68078)] computing only one farthest neighbor per vertex. As a by-product a linear-time algorithm for all symmetric farthest neighbor pairs for a simple polygon is obtained (``symmetric means that the two vertices are farthest neighbors of each other).

Recommendations

• Computing geodesic furthest neighbors in simple polygons
• Computing external farthest neighbors for a simple polygon
• An \(O(n\log n)\) algorithm for the all-farthest-segments problem for a planar set of points
• scientific article; zbMATH DE number 1796963
• PARALLEL COMPUTATION OF INTERNAL AND EXTERNAL FARTHEST NEIGHBORS IN SIMPLE POLYGONS

Cites work

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

Cited in

(14)

• Computing external farthest neighbors for a simple polygon
• An optimal parallel algorithm for computing furthest neighbors in a tree
• Computing farthest neighbors on a convex polytope.
• On computing the optimal bridge between two convex polygons.
• Farthest-point queries with geometric and combinatorial constraints
• Selection and sorting in totally monotone arrays
• PARALLEL COMPUTATION OF INTERNAL AND EXTERNAL FARTHEST NEIGHBORS IN SIMPLE POLYGONS
• Linear algorithm to find the largest intriangles of a planar convex polygon
• Base station placement on boundary of a convex polygon
• An efficient algorithm for the three-dimensional diameter problem
• The symmetric all-furthest-neighbor problem
• On the angle restricted nearest neighbor problem
• An optimal algorithm with unknown time complexity for convex matrix searching
• Finding all nearest neighbors for convex polygons in parallel: A new lower bound technique and a matching algorithm

This page was built for publication: A linear time algorithm for finding all farthest neighbors in a convex polygon

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