Simplex range reporting on a pointer machine

DOI10.1016/0925-7721(95)00002-XzbMath0851.68113MaRDI QIDQ1917035

Bernard Chazelle, Burton Rosenberg

Publication date: 14 July 1996

Published in: Computational Geometry (Search for Journal in Brave)

zbMATH Keywords

simplex range reporting

Mathematics Subject Classification ID

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

Related Items (12)

Lower bounds for off-line range searching ⋮ Lower bounds for intersection searching and fractional cascading in higher dimension ⋮ Polynomial Data Structure Lower Bounds in the Group Model ⋮ An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³ ⋮ On semialgebraic range reporting ⋮ Rectangle stabbing and orthogonal range reporting lower bounds in moderate dimensions ⋮ Optimal partition trees ⋮ Simplex Range Searching and Its Variants: A Review ⋮ Unnamed Item ⋮ New lower bounds for Hopcroft's problem ⋮ Top tree compression of tries ⋮ IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS

Cites Work

• Unnamed Item
• Unnamed Item
• A class of algorithms which require nonlinear time to maintain disjoint sets
• \(\epsilon\)-nets and simplex range queries
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time
• Polygonal intersection searching
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Quasi-optimal range searching in spaces of finite VC-dimension
• Lower Bounds on the Complexity of Polytope Range Searching
• Lower bounds for orthogonal range searching: I. The reporting case
• Filtering Search: A New Approach to Query-Answering
• Point retrieval for polygons
• Polygon Retrieval
• On Heilbronn's Triangle Problem
• A Lower Bound for Heilbronn'S Problem

This page was built for publication: Simplex range reporting on a pointer machine