IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS

DOI10.1142/S0218195913600054zbMath1300.68051MaRDI QIDQ2875643

Peyman Afshani

Publication date: 11 August 2014

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

zbMATH Keywords

lower boundsrange searchingpointer machineI/O model

Mathematics Subject Classification ID

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

Related Items (2)

An (Almost) Optimal Solution for Orthogonal Point Enclosure Query in ℝ³ ⋮ Simplex Range Searching and Its Variants: A Review

Cites Work

• Tight lower bounds for halfspace range searching
• Range searching with efficient hierarchical cuttings
• A deterministic view of random sampling and its use in geometry
• Optimal external memory planar point enclosure
• Efficient partition trees
• Quasi-optimal upper bounds for simplex range searching and new zone theorems
• Cutting hyperplanes for divide-and-conquer
• Efficient searching with linear constraints
• New applications of random sampling in computational geometry
• Lower bounds for intersection searching and fractional cascading in higher dimension
• Simplex range reporting on a pointer machine
• On a model of indexability and its bounds for range queries
• Lower bounds for orthogonal range searching: I. The reporting case
• Filtering Search: A New Approach to Query-Answering
• Polygon Retrieval
• Space-Time Tradeoffs for Emptiness Queries

This page was built for publication: IMPROVED POINTER MACHINE AND I/O LOWER BOUNDS FOR SIMPLEX RANGE REPORTING AND RELATED PROBLEMS