Ray Shooting and Parametric Search
From MaRDI portal
Publication:3137709
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
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
