Computing farthest neighbors on a convex polytope.

DOI10.1016/S0304-3975(02)00431-0zbMath1044.68150MaRDI QIDQ1401257

Antoine Vigneron, Chan-Su Shin, Otfried Schwarzkopf

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

Computational geometry3DFarthest neighborsFarthest-point Voronoi DiagramPolytope

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items

Group nearest-neighbor queries in the \(L_1\) plane ⋮ Farthest-point queries with geometric and combinatorial constraints ⋮ On Some Proximity Problems of Colored Sets

Cites Work

• Unnamed Item
• An O(n log n) algorithm for the all-nearest-neighbors problem
• A linear time algorithm for finding all farthest neighbors in a convex polygon
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions
• Applications of random sampling in computational geometry. II
• Deterministic algorithms for 3-D diameter and some 2-D lower envelopes
• An efficient algorithm for the three-dimensional diameter problem