On counting pairs of intersecting segments and off-line triangle range searching

DOI10.1007/BF02523679MaRDI QIDQ676268zbMATH OpenOpenAlexFDO

Authors Marco Pellegrini

Publication date 16 March 1997

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf02523679

zbMATH Keywords

bichromatic intersecting segmentsderandomizationmonochromatic intersection points

Mathematics Subject Classification ID

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

Recommendations

• Reporting and counting segment intersections
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• Line arrangements and range search
• scientific article; zbMATH DE number 4062593

Cites work

• -nets and simplex range queries
• A deterministic view of random sampling and its use in geometry
• A generic algorithm for one-dimensional homotopic compaction
• Algorithms for bichromatic line-segment problems and polyhedral terrains
• Algorithms for Reporting and Counting Geometric Intersections
• An optimal algorithm for intersecting line segments in the plane
• Applications of random sampling in computational geometry. II
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Cutting hyperplane arrangements
• Cutting hyperplanes for divide-and-conquer
• CUTTINGS AND APPLICATIONS
• Efficient partition trees
• Geometric retrieval problems
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 4032498 (Why is no real title available?)
• scientific article; zbMATH DE number 4062593 (Why is no real title available?)
• scientific article; zbMATH DE number 1263252 (Why is no real title available?)
• scientific article; zbMATH DE number 1032051 (Why is no real title available?)
• Lower Bounds on the Complexity of Polytope Range Searching
• New applications of random sampling in computational geometry
• On Collision-Free Placements of Simplices and the Closest Pair of Lines in 3-Space
• On point location and motion planning among simplices
• On the Zone Theorem for Hyperplane Arrangements
• On Vertical Visibility in Arrangements of Segments and the Queue Size in the Bentley-Ottmann Line Sweeping Algorithm
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Partitioning arrangements of lines. II: Applications
• Plane-sweep algorithms for intersecting geometric figures
• Polygon Retrieval
• Quasi-optimal range searching in spaces of finite VC-dimension
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Red-Blue Intersection Detection Algorithms, with Applications to Motion Planning and Collision Detection
• Reporting and counting segment intersections

Cited in

(9)

• Algorithms for bichromatic line-segment problems and polyhedral terrains
• Counting and representing intersections among triangles in three dimensions
• On the Zarankiewicz problem for intersection hypergraphs
• Good splitters for counting points in triangles
• ON ENUMERATING AND SELECTING DISTANCES
• Counting circles without computing them
• Counting and representing intersections among triangles in three dimensions
• scientific article; zbMATH DE number 6297698 (Why is no real title available?)
• Cuttings for disks and axis-aligned rectangles in three-space

This page was built for publication: On counting pairs of intersecting segments and off-line triangle range searching

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q676268)