Storing line segments in partition trees
From MaRDI portal
Publication:911289
DOI10.1007/BF01931656zbMATH Open0696.68068OpenAlexW2136688261MaRDI QIDQ911289FDOQ911289
Authors: Mark H. Overmars, Haijo Schipper, Micha Sharir 
Publication date: 1990
Published in: BIT (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01931656
Recommendations
- Hyper-rectangular space partitioning trees: practical approach
- Efficient partition trees
- scientific article; zbMATH DE number 2119698
- Binary Space Partitions for Line Segments with a Limited Number of Directions
- Partitioning points by parallel planes
- Partitioning point sets in arbitrary dimension
- scientific article; zbMATH DE number 4049401
- Partitioning arrangements of lines. I: An efficient deterministic algorithm
- Space-efficient vertex separators for treewidth
intersection queriesinterval partition treesray shooting queriessegment partition treestriangle stabbing queries
Cites Work
- Title not available (Why is that?)
- \(\epsilon\)-nets and simplex range queries
- Title not available (Why is that?)
- On the general motion-planning problem with two degrees of freedom
- Priority Search Trees
- Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
- A Functional Approach to Data Structures and Its Use in Multidimensional Searching
- Visibility and intersection problems in plane geometry
- Halfplanar range search in linear space and \(O(n^{0.695})\) query time
- Implicitly representing arrangements of lines or segments
- Quasi-optimal range searching in spaces of finite VC-dimension
- Polygon Retrieval
- Planar realizations of nonlinear Davenport-Schinzel sequences by segments
- Separating two simple polygons by a sequence of translations
- An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
- Title not available (Why is that?)
- Space searching for intersecting objects
- Storing line segments in partition trees
Cited In (15)
- Storing line segments in partition trees
- Point enclosure problem for homothetic polygons
- Efficient ray shooting and hidden surface removal
- Range searching with efficient hierarchical cuttings
- Algorithms for subpath convex hull queries and ray-shooting among segments
- Enhanced layered segment trees: a pragmatic data structure for real-time processing of geometric objects
- Direct dynamic structures for some line segment problems
- A note on small linear-ordering polytopes
- Title not available (Why is that?)
- Connected component and simple polygon intersection searching
- Approximate range searching using binary space partitions
- Dynamic partition trees
- Intersection queries in sets of disks
- Intersection queries in sets of disks
- Dynamic partition trees
This page was built for publication: Storing line segments in partition trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q911289)
