On counting pairs of intersecting segments and off-line triangle range searching
From MaRDI portal
Publication:676268
DOI10.1007/BF02523679zbMath0869.68116OpenAlexW2053735114MaRDI QIDQ676268
Publication date: 16 March 1997
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf02523679
Related Items (4)
On the Zarankiewicz problem for intersection hypergraphs ⋮ Cuttings for disks and axis-aligned rectangles in three-space ⋮ ON ENUMERATING AND SELECTING DISTANCES ⋮ Counting and representing intersections among triangles in three dimensions
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A deterministic view of random sampling and its use in geometry
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- A generic algorithm for one-dimensional homotopic compaction
- Partitioning arrangements of lines. II: Applications
- \(\epsilon\)-nets and simplex range queries
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Cutting hyperplane arrangements
- Efficient partition trees
- Quasi-optimal upper bounds for simplex range searching and new zone theorems
- Cutting hyperplanes for divide-and-conquer
- Algorithms for bichromatic line-segment problems and polyhedral terrains
- New applications of random sampling in computational geometry
- Reporting and counting segment intersections
- Applications of random sampling in computational geometry. II
- Quasi-optimal range searching in spaces of finite VC-dimension
- On point location and motion planning among simplices
- Algorithms for Reporting and Counting Geometric Intersections
- Lower Bounds on the Complexity of Polytope Range Searching
- Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
- Geometric retrieval problems
- Constructing Arrangements of Lines and Hyperplanes with Applications
- Polygon Retrieval
- Plane-sweep algorithms for intersecting geometric figures
- On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
- On the Zone Theorem for Hyperplane Arrangements
- On Collision-Free Placements of Simplices and the Closest Pair of Lines in 3-Space
- An optimal algorithm for intersecting line segments in the plane
- CUTTINGS AND APPLICATIONS
This page was built for publication: On counting pairs of intersecting segments and off-line triangle range searching
