Storing line segments in partition trees
type: Item
instance of: scholarly article
title: Storing line segments in partition trees
zbMATH Open document ID: 0696.68068
DOI: 10.1007/BF01931656
author: Mark H. Overmars
author: Haijo Schipper
author: Micha Sharir
published in: BIT
publication date: 1990-01-01T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68P05
zbMATH DE Number: 4141509
zbMATH Keywords: segment partition trees
zbMATH Keywords: interval partition trees
zbMATH Keywords: intersection queries
zbMATH Keywords: triangle stabbing queries
zbMATH Keywords: ray shooting queries
MaRDI profile type: Publication
cites work: A Functional Approach to Data Structures and Its Use in Multidimensional Searching
cites work: Visibility and intersection problems in plane geometry
cites work: Quasi-optimal range searching in spaces of finite VC-dimension
cites work: Space searching for intersecting objects
cites work: Q3772828
cites work: Implicitly representing arrangements of lines or segments
cites work: Halfplanar range search in linear space and \(O(n^{0.695})\) query time
cites work: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons
cites work: Q3796750
cites work: On the general motion-planning problem with two degrees of freedom
cites work: \(\epsilon\)-nets and simplex range queries
cites work: Priority Search Trees
cites work: Separating two simple polygons by a sequence of translations
cites work: Q3694703
cites work: An $O(n\log \log n)$-Time Algorithm for Triangulating a Simple Polygon
cites work: Planar realizations of nonlinear Davenport-Schinzel sequences by segments
cites work: Polygon Retrieval
full work available at URL: https://doi.org/10.1007/bf01931656
OpenAlex ID: W2136688261
Recommended article: Hyper-rectangular space partitioning trees: practical approach
Recommended article: Efficient partition trees
Recommended article: Q4828969
Recommended article: Binary Space Partitions for Line Segments with a Limited Number of Directions
Recommended article: Partitioning points by parallel planes
Recommended article: Partitioning point sets in arbitrary dimension
Recommended article: Q3786288
Recommended article: Partitioning arrangements of lines. I: An efficient deterministic algorithm
Recommended article: Space-efficient vertex separators for treewidth
description: scientific article; zbMATH DE number 4141509