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

DOI10.1137/21M145118XMaRDI QIDQ6593765FDOQ6593765

Publication date: 27 August 2024

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

convex hulls ray-shooting compact interval trees subpath hull queries

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

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

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)