RANDOMIZED EXTERNAL-MEMORY ALGORITHMS FOR LINE SEGMENT INTERSECTION AND OTHER GEOMETRIC PROBLEMS

DOI10.1142/S0218195901000523zbMath1074.68669MaRDI QIDQ4682170

Paolo Ferragina, A. Crauser, Kurt Mehlhorn, Ulrich Meyer, Edgar A. Ramos

Publication date: 10 June 2005

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

randomized algorithms; external memory; Line segment intersections

Mathematics Subject Classification ID

68U05: Computer graphics; computational geometry (digital and algorithmic aspects)

68W20: Randomized algorithms

Related Items

I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions, I/O-efficient point location using persistent B-trees, I/O-efficient algorithms for computing planar geometric spanners, Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection, Efficient searching with linear constraints, I/O-efficient dynamic planar point location, Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions

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