Farthest-point queries with geometric and combinatorial constraints

DOI10.1016/j.comgeo.2005.07.002zbMath1113.65019OpenAlexW2098197750MaRDI QIDQ2489542

Alexander Wolff, Ovidiu Daescu, Ningfang Mi, Chan-Su Shin

Publication date: 28 April 2006

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://idus.us.es/xmlui/handle/11441/55045

zbMATH Keywords

Farthest-point queriesLine-segment queriesPolygonal path simplification

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (7)

Approximating the discrete center line segment in linear time ⋮ Trajectory planning for an articulated probe ⋮ Constrained minimum enclosing circle with center on a query line segment ⋮ Optimal simplification of polygonal chains for subpixel-accurate rendering ⋮ Data structures for halfplane proximity queries and incremental Voronoi diagrams ⋮ On the minimum total length of interval systems expressing all intervals, and range-restricted queries ⋮ BASELINE BOUNDED HALF-PLANE VORONOI DIAGRAM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polygonal chain approximation: A query based approach
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• The power of geometric duality revisited
• 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
• Efficient partition trees
• Computing farthest neighbors on a convex polytope.
• Facility location and the geometric minimum-diameter spanning tree.
• Queries with segments in Voronoi diagrams
• Efficient algorithms for approximating polygonal chains
• Geometric retrieval problems
• Optimal Point Location in a Monotone Subdivision
• Efficiently computing the closest point to a query line
• SPACE-EFFICIENT ALGORITHMS FOR APPROXIMATING POLYGONAL CURVES IN TWO-DIMENSIONAL SPACE
• COMPUTING CLOSEST POINTS FOR SEGMENTS
• APPROXIMATION OF POLYGONAL CURVES WITH MINIMUM NUMBER OF LINE SEGMENTS OR MINIMUM ERROR

This page was built for publication: Farthest-point queries with geometric and combinatorial constraints