Vertical decompositions for triangles in 3-space
From MaRDI portal
Publication:1907609
DOI10.1007/BF02716578zbMath0840.68116OpenAlexW1993965377MaRDI 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)
Full work available at URL: https://doi.org/10.1007/bf02716578
Analysis of algorithms and problem complexity (68Q25) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Related Items (11)
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 ⋮ Almost tight upper bounds for the single cell and zone problems in the three dimensions ⋮ Vertical decompositions for triangles in 3-space ⋮ Throwing a sofa through the window ⋮ Translational packing of arbitrary polytopes ⋮ A new technique for analyzing substructures in arrangements of piecewise linear surfaces ⋮ Spheres, molecules, and hidden surface removal ⋮ Dynamic motion planning in low obstacle density environments ⋮ Dynamic motion planning in low obstacle density environments ⋮ 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
This page was built for publication: Vertical decompositions for triangles in 3-space
