Storing line segments in partition trees

DOI10.1007/BF01931656zbMath0696.68068OpenAlexW2136688261MaRDI QIDQ911289

Haijo Schipper, Mark H. Overmars, Micha Sharir

Publication date: 1990

Published in: BIT (Search for Journal in Brave)

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

zbMATH Keywords

intersection queriesinterval partition treesray shooting queriessegment partition treestriangle stabbing queries

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Data structures (68P05)

Related Items

Efficient ray shooting and hidden surface removal, A note on small linear-ordering polytopes, Connected component and simple polygon intersection searching, Point enclosure problem for homothetic polygons, Storing line segments in partition trees, Intersection queries in sets of disks, Range searching with efficient hierarchical cuttings, Dynamic partition trees, Approximate range searching using binary space partitions, Intersection queries in sets of disks, Dynamic partition trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Visibility and intersection problems in plane geometry
• Storing line segments in partition trees
• \(\epsilon\)-nets and simplex range queries
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Planar realizations of nonlinear Davenport-Schinzel sequences by segments
• Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
• Separating two simple polygons by a sequence of translations
• On the general motion-planning problem with two degrees of freedom
• Implicitly representing arrangements of lines or segments
• Quasi-optimal range searching in spaces of finite VC-dimension
• Priority Search Trees
• An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
• Polygon Retrieval
• A Functional Approach to Data Structures and Its Use in Multidimensional Searching
• Space searching for intersecting objects