Ray Shooting and Parametric Search

DOI10.1137/0222051zbMath0777.68042OpenAlexW2016400774MaRDI QIDQ3137709

Ji{ří} Matoušek, Pankaj K. Agarwal

Publication date: 10 October 1993

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

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

zbMATH Keywords

convex polytopearrangementrange searchingparametric searchray shooting

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) (n)-dimensional polytopes (52B11) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10) Data structures (68P05)

Related Items

On range searching with semialgebraic sets ⋮ Linear data structures for fast ray-shooting amidst convex polyhedra ⋮ PROCESSING AN OFFLINE INSERTION-QUERY SEQUENCE WITH APPLICATIONS ⋮ Dynamic half-space range reporting and its applications ⋮ Selection in monotone matrices and computing k th nearest neighbors ⋮ Monte Carlo approximation of form factors with error bounded a priori ⋮ Vertical decompositions for triangles in 3-space ⋮ Processing an Offline Insertion-Query Sequence with Applications ⋮ On Ray Shooting for Triangles in 3-Space and Related Problems ⋮ Nearest-neighbor searching under uncertainty. I ⋮ Maximum matchings in geometric intersection graphs ⋮ Approximate Polytope Membership Queries ⋮ Range minima queries with respect to a random permutation, and approximate range counting ⋮ Simplex Range Searching and Its Variants: A Review ⋮ OBNOXIOUS FACILITY LOCATION: COMPLETE SERVICE WITH MINIMAL HARM ⋮ Linear approximation of simple objects ⋮ A faster algorithm for computing motorcycle graphs ⋮ Dynamic geometric data structures via shallow cuttings ⋮ Ray shooting and intersection searching amidst fat convex polyhedra in 3-space ⋮ Shortest rectilinear path queries to rectangles in a rectangular domain ⋮ Output-sensitive peeling of convex and maximal layers ⋮ Dynamic output-sensitive hidden surface removal for \(c\)-oriented polyhedra ⋮ Applications of a new space-partitioning technique ⋮ Efficient partition trees ⋮ Efficient hidden surface removal for objects with small union size ⋮ Approximating nearest neighbor among triangles in convex position ⋮ Computing the visibility map of fat objects ⋮ Ray shooting and stone throwing with near-linear storage ⋮ POLYLINE FITTING OF PLANAR POINTS UNDER MIN-SUM CRITERIA ⋮ Output-sensitive results on convex hulls, extreme points, and related problems ⋮ Dynamic ham-sandwich cuts in the plane ⋮ Approximating Minimization Diagrams and Generalized Proximity Search ⋮ An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction ⋮ An Output-Sensitive Convex Hull Algorithm for Planar Objects ⋮ THE OBJECT COMPLEXITY MODEL FOR HIDDEN-SURFACE REMOVAL