RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
From MaRDI portal
Publication:4682170
DOI10.1142/S0218195901000523zbMATH Open1074.68669MaRDI QIDQ4682170FDOQ4682170
Authors: A. Crauser, Paolo Ferragina, K. Mehlhorn, Ulrich Meyer, Edgar A. Ramos 
Publication date: 10 June 2005
Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)
Recommendations
- Efficient dynamic algorithms for some geometric intersection problems
- scientific article; zbMATH DE number 1424304
- scientific article; zbMATH DE number 1419216
- Optimal randomized parallel algorithms for computational geometry
- An optimal algorithm for intersecting line segments in the plane
- Tail estimates for the efficiency of randomized incremental algorithms for line segment intersection
- Towards dynamic randomized algorithms in computational geometry
- scientific article; zbMATH DE number 1424315
- External-memory algorithms for processing line segments in geographic information systems
- scientific article; zbMATH DE number 410386
Randomized algorithms (68W20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)
Cites Work
- \(\epsilon\)-nets and simplex range queries
- An optimal convex hull algorithm in any fixed dimension
- Applications of random sampling in computational geometry. II
- The string B-tree
- A deterministic view of random sampling and its use in geometry
- An optimal algorithm for intersecting line segments in the plane
- On finite-precision representations of geometric objects
- Algorithms for parallel memory, I: Two-level memories
- Product Range Spaces, Sensitive Sampling, and Derandomization
- Efficient perturbations for handling geometric degeneracies
- Cutting hyperplane arrangements
- Dynamic point location in arrangements of hyperplanes
- Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
- RANDOMIZED PARALLEL ALGORITHMS FOR TRAPEZOIDAL DIAGRAMS
- Derandomization in Computational Geometry
Cited In (16)
- Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions
- Title not available (Why is that?)
- Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
- Efficient searching with linear constraints
- Title not available (Why is that?)
- External-memory algorithms for processing line segments in geographic information systems
- Permuting and batched geometric lower bounds in the I/O model
- Title not available (Why is that?)
- A random direction algorithm for an intersection problem
- Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep
- External-memory algorithms for processing line segments in geographic information systems
- I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions
- I/O-efficient algorithms for computing planar geometric spanners
- I/O-efficient dynamic planar point location
- I/O-efficient point location using persistent B-trees
- External memory planar point location with logarithmic updates
This page was built for publication: RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4682170)
