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

DOI10.1142/S0218195901000523MaRDI QIDQ4682170zbMATH OpenFDO

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)

zbMATH Keywords

randomized algorithmsexternal memoryLine segment intersections

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

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

Cites work

• A deterministic view of random sampling and its use in geometry
• Algorithms for parallel memory, I: Two-level memories
• An optimal algorithm for intersecting line segments in the plane
• An optimal convex hull algorithm in any fixed dimension
• Applications of random sampling in computational geometry. II
• Cutting hyperplane arrangements
• Derandomization in Computational Geometry
• Dynamic point location in arrangements of hyperplanes
• Efficient perturbations for handling geometric degeneracies
• On finite-precision representations of geometric objects
• Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems
• Product Range Spaces, Sensitive Sampling, and Derandomization
• RANDOMIZED PARALLEL ALGORITHMS FOR TRAPEZOIDAL DIAGRAMS
• The string B-tree
• \(\epsilon\)-nets and simplex range queries

Cited in

(16)

• scientific article; zbMATH DE number 1424323 (Why is no real title available?)
• Optimal in-place and cache-oblivious algorithms for 3-D convex hulls and 2-D segment intersection
• I/O-Efficient Map Overlay and Point Location in Low-Density Subdivisions
• Efficient searching with linear constraints
• A random direction algorithm for an intersection problem
• I/O-efficient point location using persistent B-trees
• External memory planar point location with logarithmic updates
• Star-quadtrees and guard-quadtrees: I/O-efficient indexes for fat triangulations and low-density planar subdivisions
• Experiments on the practical I/O efficiency of geometric algorithms: Distribution sweep vs. plane sweep
• I/O-efficient algorithms for computing planar geometric spanners
• External-memory algorithms for processing line segments in geographic information systems
• I/O-efficient dynamic planar point location
• External-memory algorithms for processing line segments in geographic information systems
• Permuting and batched geometric lower bounds in the I/O model
• scientific article; zbMATH DE number 1555971 (Why is no real title available?)
• scientific article; zbMATH DE number 4082961 (Why is no real title available?)

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)