RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
From MaRDI portal
Publication:4682170
DOI10.1142/S0218195901000523zbMath1074.68669MaRDI QIDQ4682170
Ulrich Meyer, Paolo Ferragina, Kurt Mehlhorn, A. Crauser, Edgar A. Ramos
Publication date: 10 June 2005
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Randomized algorithms (68W20)
Related Items (9)
I/O-efficient dynamic planar point location ⋮ I/O-efficient algorithms for computing planar geometric spanners ⋮ I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions ⋮ Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions ⋮ Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection ⋮ I/O-efficient point location using persistent B-trees ⋮ External memory planar point location with logarithmic updates ⋮ Permuting and Batched Geometric Lower Bounds in the I/O Model ⋮ Efficient searching with linear constraints
Cites Work
- On finite-precision representations of geometric objects
- A deterministic view of random sampling and its use in geometry
- \(\epsilon\)-nets and simplex range queries
- Cutting hyperplane arrangements
- Dynamic point location in arrangements of hyperplanes
- An optimal convex hull algorithm in any fixed dimension
- Algorithms for parallel memory, I: Two-level memories
- Efficient perturbations for handling geometric degeneracies
- Applications of random sampling in computational geometry. II
- The string B-tree
- Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
- RANDOMIZED PARALLEL ALGORITHMS FOR TRAPEZOIDAL DIAGRAMS
- Product Range Spaces, Sensitive Sampling, and Derandomization
- An optimal algorithm for intersecting line segments in the plane
- Derandomization in Computational Geometry
This page was built for publication: RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
