Partitioning Space for Range Queries

DOI10.1137/0218025MaRDI QIDQ3830566zbMATH OpenOpenAlexFDO

Authors F. Frances Yao, David P. Dobkin, Michael S. Paterson, Herbert Edelsbrunner

Publication date 1989

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://wrap.warwick.ac.uk/60814/12/WRAP_cs-rr-118.pdf

zbMATH Keywords

Borsuk-Ulam theoremequipartitionhalf-space querypartitionrange query

Mathematics Subject Classification ID

Fixed-point and coincidence theorems (topological aspects) (54H25) Fixed points and coincidences in algebraic topology (55M20) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Recommendations

• Efficient partition trees
• Partitioning point sets in arbitrary dimension
• Quasi-optimal range searching in spaces of finite VC-dimension
• Non-partitionable point sets
• Halfplanar range search in linear space and \(O(n^{0.695})\) query time

Cited in

(23)

• Non-partitionable point sets
• The farthest point Delaunay triangulation minimizes angles
• Counting facets and incidences
• An equipartition of planar sets
• Hyperplane equipartitions plus constraints
• Equipartition of mass distributions by hyperplanes
• Some combinatorial and algorithmic applications of the Borsuk-Ulam theorem
• Optimal partition trees
• scientific article; zbMATH DE number 1945834 (Why is no real title available?)
• Topology of the Grünbaum–Hadwiger–Ramos hyperplane mass partition problem
• Simplex Range Searching and Its Variants: A Review
• Equipartitions and Mahler volumes of symmetric convex bodies
• A survey of mass partitions
• Measure partitions via Fourier analysis. II: Center transversality in the \({{L}^{2}}\)-norm for complex hyperplanes
• Equipartitions of measures in $\mathbb{R}^4$
• Partitioning axis-parallel lines in 3D
• Eight-partitioning points in 3D, and efficiently too
• The generalized Makeev problem revisited
• On the orthogonal Grünbaum partition problem in dimension three
• Eight-partitioning points in 3D, and efficiently too
• A deterministic partition tree and applications
• Topology and combinatorics of partitions of masses by hyperplanes
• Measure equipartitions via finite Fourier analysis

This page was built for publication: Partitioning Space for Range Queries

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3830566)