Proximity problems on line segments spanned by points

DOI10.1016/J.COMGEO.2005.08.007MaRDI QIDQ2489537zbMATH OpenOpenAlexFDO

Authors Ovidiu Daescu, Jun Luo, David M. Mount

Publication date 28 April 2006

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2005.08.007

zbMATH Keywords

algorithm

Mathematics Subject Classification ID

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

Review text

Given a set \(S\) of \(n\) points and another point \(q\), the authors study the problem of finding the closest or farthest line segment (line) from \(q\) among those spanned by points in \(S\). They present an algorithm with \(O(n\log n)\) time and \(O(n)\) space for computing an optimal solution.

Recommendations

• Computing closest and farthest points for a query segment
• COMPUTING CLOSEST POINTS FOR SEGMENTS
• scientific article; zbMATH DE number 1424308
• Queries with segments in Voronoi diagrams
• scientific article; zbMATH DE number 1305399

Cites work

• A RANDOMIZED ALGORITHM FOR SLOPE SELECTION
• A tight bound for the number of different directions in three dimensions
• An Expander-Based Approach to Geometric Optimization
• An Optimal-Time Algorithm for Slope Selection
• Efficient randomized algorithms for robust estimation of circular arcs and aligned ellipses
• Farthest-Point Queries with Geometric and Combinatorial Constraints
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3482343 (Why is no real title available?)
• scientific article; zbMATH DE number 732977 (Why is no real title available?)
• scientific article; zbMATH DE number 1049272 (Why is no real title available?)
• Off-Line Maintenance of Planar Configurations
• ON ENUMERATING AND SELECTING DISTANCES
• Optimal slope selection via cuttings
• Randomized optimal algorithm for slope selection
• Selecting distances in arrangements of hyperplanes spanned by points.
• Separating objects in the plane by wedges and strips
• SIMPLE ALGORITHMS FOR ENUMERATING INTERPOINT DISTANCES AND FINDING k NEAREST NEIGHBORS
• Solution of Scott's problem on the number of directions determined by a point set in 3-space

Cited in

(14)

• Optimal time bounds for some proximity problems in the plane
• Largest and smallest area triangles on imprecise points
• Computing Euclidean Steiner trees over segments
• An \(O(n\log n)\) algorithm for the all-farthest-segments problem for a planar set of points
• Computing closest and farthest points for a query segment
• Extremal point queries with lines and line segments and related problems
• Proximity on equilateral spaces
• All-maximum and all-minimum problems under some measures
• Multidimensional Lines II: Proximity and Applications
• COMPUTING CLOSEST POINTS FOR SEGMENTS
• scientific article; zbMATH DE number 1424308 (Why is no real title available?)
• On the all-farthest-segments problem for a planar set of points
• Farthest line segment Voronoi diagrams
• Farthest segments and extremal triangles spanned by points in \(\mathbb R^3\)

This page was built for publication: Proximity problems on line segments spanned by points

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