Algorithms for subpath convex hull queries and ray-shooting among segments

DOI10.1137/21M145118XMaRDI QIDQ6593765zbMATH OpenFDO

Authors Haitao Wang

Publication date 27 August 2024

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/21M145118X

zbMATH Keywords

convex hullsray-shootingcompact interval treessubpath hull queries

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Cites work

• scientific article; zbMATH DE number 4062593 (Why is no real title available?)
• scientific article; zbMATH DE number 176570 (Why is no real title available?)
• scientific article; zbMATH DE number 1256697 (Why is no real title available?)
• scientific article; zbMATH DE number 1512678 (Why is no real title available?)
• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• Algorithms for ray-shooting and intersection searching
• An optimal algorithm for the boundary of a cell in a union of rays
• Applications of a new space-partitioning technique
• Approximating points by a piecewise linear function
• COMPACT INTERVAL TREES: A DATA STRUCTURE FOR CONVEX HULLS
• Computational geometry. Algorithms and applications.
• Cutting hyperplane arrangements
• Cutting hyperplanes for divide-and-conquer
• Efficient algorithms for the one-dimensional \(k\)-center problem
• Efficient partition trees
• Enclosing a Set of Objects by Two Minimum Area Rectangles
• Fast Algorithms for Finding Nearest Common Ancestors
• Finding the convex hull of a simple polygon
• Fractional cascading. II: Applications
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Implicitly representing arrangements of lines or segments
• Improved bounds for wireless localization
• Making data structures persistent
• On top-\(k\) weighted sum aggregate nearest and farthest neighbors in the \(L_1\) plane
• On-line construction of the convex hull of a simple polyline
• Optimal Point Location in a Monotone Subdivision
• Optimal Search in Planar Subdivisions
• Optimal partition trees
• Optimal time-convex hull under the \(L _{p }\) metrics
• Quasi-optimal range searching in spaces of finite VC-dimension
• Range searching with efficient hierarchical cuttings
• Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number
• Ray shooting in polygons using geodesic triangulations
• Storing line segments in partition trees
• Visibility and intersection problems in plane geometry

Cited in

(1)

• Algorithms for computing closest points for segments

This page was built for publication: Algorithms for subpath convex hull queries and ray-shooting among segments

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