Dynamic partition trees

DOI10.1007/BF01933260zbMath0727.68042MaRDI QIDQ804289

Mark H. Overmars, Haijo Schipper

Publication date: 1991

Published in: BIT (Search for Journal in Brave)

zbMATH Keywords

shootingconjugation treeshalf-planar range searchingintersection queries

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Data structures (68P05)

Related Items (2)

An optimal algorithm for reporting visible rectangles ⋮ An improved technique for output-sensitive hidden surface removal

Cites Work

• Unnamed Item
• Unnamed Item
• The design of dynamic data structures
• 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
• Decomposable searching problems
• An improved technique for output-sensitive hidden surface removal
• Priority Search Trees
• Partitioning with two lines in the plane
• Polygon Retrieval
• A simple output-sensitive algorithm for hidden surface removal

This page was built for publication: Dynamic partition trees