Polygonal intersection searching
From MaRDI portal
Publication:1165007
DOI10.1016/0020-0190(82)90090-4zbMath0486.68051OpenAlexW2092286433MaRDI QIDQ1165007
Herbert Edelsbrunner, David G. Kirkpatrick, Hermann Maurer
Publication date: 1982
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(82)90090-4
geometric searchingconcrete complexitymulti-dimensional searchinggeometric transformspolygon intersectiontriangular range searching
Related Items
The power of geometric duality, Halfplanar range search in linear space and \(O(n^{0.695})\) query time, Fractional cascading. II: Applications, Simplex range reporting on a pointer machine, Simplex Range Searching and Its Variants: A Review, Stabbing line segments, A polynomial-time algorithm for computing the yolk in fixed dimension, Lower bounds on the complexity of simplex range reporting on a pointer machine, The intersection searching problem for c-oriented polygons, On the number of line separations of a finite set in the plane, Optimal solutions for a class of point retrieval problems, The power of geometric duality revisited
Cites Work
- Multidimensional divide-and-conquer
- Finding extreme points in three dimensions and solving the post-office problem in the plane
- Efficient worst-case data structures for range searching
- A space-optimal solution of general region location
- Algorithms for Reporting and Counting Geometric Intersections
- New Data Structures for Orthogonal Range Queries
- A Note on Locating a Set of Points in a Planar Subdivision
- Comments on “algorithms for reporting and counting geometric intersections”
- Counting and Reporting Intersections of d-Ranges
- Rectilinear line segment intersection, layered segment trees, and dynamization
- Plane-sweep algorithms for intersecting geometric figures
- Multidimensional Searching Problems
