Vertical decompositions for triangles in 3-space
From MaRDI portal
Publication:1907609
DOI10.1007/BF02716578zbMath0840.68116MaRDI QIDQ1907609
Dan Halperin, Leonidas J. Guibas, Mark T. de Berg
Publication date: 13 February 1996
Published in: Discrete \& Computational Geometry (Search for Journal in Brave)
68Q25: Analysis of algorithms and problem complexity
68U05: Computer graphics; computational geometry (digital and algorithmic aspects)
Related Items
Exact Minkowksi sums of polyhedra and exact and efficient decomposition of polyhedra into convex pieces, Cuttings for disks and axis-aligned rectangles in three-space, Translational packing of arbitrary polytopes, Spheres, molecules, and hidden surface removal, Dynamic motion planning in low obstacle density environments, A new technique for analyzing substructures in arrangements of piecewise linear surfaces, Almost tight upper bounds for the single cell and zone problems in the three dimensions, Vertical decompositions for triangles in 3-space, Counting and representing intersections among triangles in three dimensions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Finding the upper envelope of n line segments in O(n log n) time
- Range searching with efficient hierarchical cuttings
- A deterministic view of random sampling and its use in geometry
- Sharp upper and lower bounds on the length of general Davenport-Schinzel sequences
- Combinatorial complexity bounds for arrangements of curves and spheres
- The upper envelope of piecewise linear functions: Tight bounds on the number of faces
- \(\epsilon\)-nets and simplex range queries
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Fractional cascading. I: A data structuring technique
- Cutting hyperplanes for divide-and-conquer
- Ray shooting, depth orders and hidden surface removal
- On range searching with semialgebraic sets
- Efficient ray shooting and hidden surface removal
- Castles in the air revisited
- Almost tight upper bounds for lower envelopes in higher dimensions
- Applications of random sampling in computational geometry. II
- Vertical decompositions for triangles in 3-space
- Triangles in space or building (and analyzing) castles in the air
- Algorithms for Reporting and Counting Geometric Intersections
- Ray Shooting and Parametric Search
- Convex Partitions of Polyhedra: A Lower Bound and Worst-Case Optimal Algorithm
- A Randomized Algorithm for Closest-Point Queries
- Efficient Point Location in a Convex Spatial Cell-Complex
- An optimal algorithm for intersecting line segments in the plane
- On lazy randomized incremental construction
