Polygonal intersection searching

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

zbMATH Keywords

geometric searchingconcrete complexitymulti-dimensional searchinggeometric transformspolygon intersectiontriangular range searching

Mathematics Subject Classification ID

Searching and sorting (68P10)

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