On ray shooting in convex polytopes
From MaRDI portal
Publication:685183
DOI10.1007/BF02573975zbMath0776.68110MaRDI QIDQ685183
Ji{ří} Matoušek, Otfried Schwarzkopf
Publication date: 30 September 1993
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://eudml.org/doc/131271
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)
Related Items
APPROXIMATING THE DIAMETER, WIDTH, SMALLEST ENCLOSING CYLINDER, AND MINIMUM-WIDTH ANNULUS ⋮ Kinetic sorting and kinetic convex hulls ⋮ Algorithms for generalized halfspace range searching and other intersection searching problems ⋮ Point location in zones of \(k\)-flats in arrangements ⋮ A deterministic algorithm for the three-dimensional diameter problem ⋮ On Ray Shooting for Triangles in 3-Space and Related Problems ⋮ All-maximum and all-minimum problems under some measures ⋮ A fast method for obtaining convex combination coefficients ⋮ Optimal partition trees ⋮ 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 ⋮ A tight lower bound for computing the diameter of a 3D convex polytope ⋮ An efficient algorithm for the three-dimensional diameter problem ⋮ Unnamed Item ⋮ Output-sensitive results on convex hulls, extreme points, and related problems ⋮ New lower bounds for Hopcroft's problem ⋮ Economical Delone Sets for Approximating Convex Bodies ⋮ Extremal point queries with lines and line segments and related problems ⋮ Algorithms for generalized halfspace range searching and other intersection searching problems ⋮ Unnamed Item ⋮ An Improved Ray Shooting Method for Constructive Solid Geometry Models Via Tree Contraction ⋮ An Output-Sensitive Convex Hull Algorithm for Planar Objects
Cites Work
- Unnamed Item
- Unnamed Item
- \(\epsilon\)-nets and simplex range queries
- Euclidean minimum spanning trees and bichromatic closest pairs
- Small-dimensional linear programming and convex hulls made easy
- Reporting points in halfspaces
- Efficient partition trees
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Cutting hyperplanes for divide-and-conquer
- Point location among hyperplanes and unidirectional ray-shooting
- Efficient ray shooting and hidden surface removal
- On vertical ray shooting in arrangements
- New applications of random sampling in computational geometry
- Applications of random sampling in computational geometry. II
- Lower Bounds on the Complexity of Polytope Range Searching
- How to search in history
- Applying Parallel Computation Algorithms in the Design of Serial Algorithms
- A Randomized Algorithm for Closest-Point Queries
- Decomposable searching problems I. Static-to-dynamic transformation
