Line arrangements and range search

DOI10.1016/0020-0190(88)90213-XMaRDI QIDQ1107313zbMATH OpenOpenAlexFDO

Authors Jiří Matoušek

Publication date 1988

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0190(88)90213-x

zbMATH Keywords

computational geometrygeometrical algorithmrange search

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Implicitly representing arrangements of lines or segments
• Constructing Arrangements of Lines and Hyperplanes with Applications
• Topologically sweeping an arrangement
• On range searching with semialgebraic sets
• Partitioning arrangements of lines. II: Applications

Cites work

• Constructing Belts in Two-Dimensional Arrangements with Applications
• Halfspace range search: An algorithmic application of k-sets
• scientific article; zbMATH DE number 43279 (Why is no real title available?)
• scientific article; zbMATH DE number 3407703 (Why is no real title available?)
• More on k-sets of finite sets in the plane
• New upper bounds for neighbor searching
• On the number of line separations of a finite set in the plane
• Optimal Search in Planar Subdivisions
• Reporting and counting segment intersections

Cited in

(15)

• The power of geometric duality
• Zooming by repeated range detection
• Topologically sweeping an arrangement
• Implicitly representing arrangements of lines or segments
• Finding specified sections of arrangements: 2D results
• A note on searching line arrangements and applications
• scientific article; zbMATH DE number 3936536 (Why is no real title available?)
• Constructing Belts in Two-Dimensional Arrangements with Applications
• scientific article; zbMATH DE number 1405797 (Why is no real title available?)
• Efficient and small representation of line arrangements with applications
• On finding ordinary or monochromatic intersection points
• Linear space data structures for two types of range search
• On counting pairs of intersecting segments and off-line triangle range searching
• Partitioning arrangements of lines. I: An efficient deterministic algorithm
• Partitioning arrangements of lines. II: Applications

This page was built for publication: Line arrangements and range search

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