Computing depth orders for fat objects and related problems
From MaRDI portal
Publication:1917032
DOI10.1016/0925-7721(95)00005-8zbMath0851.68102OpenAlexW2026200800MaRDI QIDQ1917032
Matthew J. Katz, Micha Sharir, Pankaj K. Agarwal
Publication date: 10 November 1996
Published in: Computational Geometry (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0925-7721(95)00005-8
Related Items (15)
Fair and square: cake-cutting in two dimensions ⋮ Models and motion planning ⋮ Generalized disk graphs ⋮ An optimal-time algorithm for shortest paths on realistic polyhedra ⋮ 3-D vertical ray shooting and 2-D point enclosure, range searching, and arc shooting amidst convex fat objects ⋮ Keep your distance: land division with separation ⋮ Piercing pairwise intersecting convex shapes in the plane ⋮ Removing depth-order cycles among triangles: an algorithm generating triangular fragments ⋮ Improved bounds on the union complexity of fat objects ⋮ A research note on design of fair surfaces over irregular domains using data-dependent triangulation ⋮ Models and motion planning ⋮ Envy-Free Division of Land ⋮ Smoothed analysis of probabilistic roadmaps ⋮ Dynamic data structures for fat objects and their applications ⋮ On the flatness of Minkowski sums
Cites Work
- Unnamed Item
- Unnamed Item
- 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
- Visibility and intersection problems in plane geometry
- An optimal algorithm for the boundary of a cell in a union of rays
- \(\epsilon\)-nets and simplex range queries
- Nonlinearity of Davenport-Schinzel sequences and of generalized path compression schemes
- Euclidean minimum spanning trees and bichromatic closest pairs
- Intersection queries in sets of disks
- Approximate motion planning and the complexity of the boundary of the union of simple geometric figures
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Efficient hidden surface removal for objects with small union size
- Ray shooting, depth orders and hidden surface removal
- Algorithms for bichromatic line-segment problems and polyhedral terrains
- On the union of fat wedges and separating a collection of segments by a line
- On range searching with semialgebraic sets
- Efficient ray shooting and hidden surface removal
- Ray shooting in polygons using geodesic triangulations
- Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
- Circle Shooting in a Simple Polygon
- Fat Triangles Determine Linearly Many Holes
- Computing and Verifying Depth Orders
- Applications of Parametric Searching in Geometric Optimization
- On fat partitioning, fat covering and the union size of polygons
This page was built for publication: Computing depth orders for fat objects and related problems
