Farthest-point queries with geometric and combinatorial constraints

DOI10.1016/J.COMGEO.2005.07.002MaRDI QIDQ2489542zbMATH OpenOpenAlexFDO

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

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)

Recommendations

• Farthest-Point Queries with Geometric and Combinatorial Constraints
• Extremal point queries with lines and line segments and related problems
• Computing closest and farthest points for a query segment
• Distance-Sensitive Planar Point Location
• On the all-farthest-segments problem for a planar set of points

Cites work

• A linear time algorithm for finding all farthest neighbors in a convex polygon
• A linear-time algorithm for computing the Voronoi diagram of a convex polygon
• An O(n log n) algorithm for the all-nearest-neighbors problem
• APPROXIMATION OF POLYGONAL CURVES WITH MINIMUM NUMBER OF LINE SEGMENTS OR MINIMUM ERROR
• COMPUTING CLOSEST POINTS FOR SEGMENTS
• Computing farthest neighbors on a convex polytope.
• Efficient algorithms for approximating polygonal chains
• Efficient partition trees
• Efficiently computing the closest point to a query line
• Facility location and the geometric minimum-diameter spanning tree.
• Farthest neighbors, maximum spanning trees and related problems in higher dimensions
• Geometric retrieval problems
• scientific article; zbMATH DE number 5542185 (Why is no real title available?)
• scientific article; zbMATH DE number 3473265 (Why is no real title available?)
• scientific article; zbMATH DE number 1947054 (Why is no real title available?)
• Optimal Point Location in a Monotone Subdivision
• Polygonal chain approximation: A query based approach
• Polygonal path approximation with angle constraints
• Queries with segments in Voronoi diagrams
• SPACE-EFFICIENT ALGORITHMS FOR APPROXIMATING POLYGONAL CURVES IN TWO-DIMENSIONAL SPACE
• The power of geometric duality revisited

Cited in

(15)

• On the minimum total length of interval systems expressing all intervals, and range-restricted queries
• Trajectory planning for an articulated probe
• Computing closest and farthest points for a query segment
• Extremal point queries with lines and line segments and related problems
• Efficient Farthest-Point Queries in Two-terminal Series-parallel Networks
• Baseline bounded half-plane Voronoi diagram
• Optimal Data Structures for Farthest-Point Queries in Cactus Networks
• Computing a Closest Point to a Query Hyperplane in Three and Higher Dimensions
• Farthest-Point Queries with Geometric and Combinatorial Constraints
• Approximating the discrete center line segment in linear time
• Algorithms for computing closest points for segments
• Algorithms for computing closest points for segments
• On the all-farthest-segments problem for a planar set of points
• Constrained minimum enclosing circle with center on a query line segment
• Optimal simplification of polygonal chains for subpixel-accurate rendering

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

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