Partitioning point sets in arbitrary dimension

DOI10.1016/0304-3975(87)90009-0MaRDI QIDQ1088420zbMATH OpenOpenAlexFDO

Authors Richard Cole

Publication date 1987

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0304-3975(87)90009-0

zbMATH Keywords

data structure for the half-space retrieval problemefficient algorithmsparallel planes partitionsearchingsublinear query time

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10) Information storage and retrieval of data (68P20)

Review text

We introduce a new type of partition called a parallel planes partition. We prove there exists a parallel planes partition of any set of n points in arbitrary dimension. This partition yields a data structure for the half-space retrieval problem in arbitrary dimension; it has linear size and achieves a sublinear query time. Also, we give efficient algorithms for computing this partition.

Recommendations

• scientific article; zbMATH DE number 3911765
• Partitioning points by parallel planes
• Efficient partition trees
• Non-partitionable point sets
• scientific article; zbMATH DE number 4213488

Cites work

• Applying Parallel Computation Algorithms in the Design of Serial Algorithms
• scientific article; zbMATH DE number 3911765 (Why is no real title available?)
• On k-Hulls and Related Problems
• Partitioning with two lines in the plane
• Polygon Retrieval
• Slowing down sorting networks to obtain faster sorting algorithms

Cited in

(12)

• Non-partitionable point sets
• Partitioning points by parallel planes
• Dispersing and grouping points on planar segments
• Splitting a configuration in a simplex
• Problem of partitioning a planar point set into empty convex polygons
• scientific article; zbMATH DE number 4213488 (Why is no real title available?)
• scientific article; zbMATH DE number 3911765 (Why is no real title available?)
• Partitioning Space for Range Queries
• SEPARATING POINT SETS IN POLYGONAL ENVIRONMENTS
• Partitioning axis-parallel lines in 3D
• The power of parallel projection
• Storing line segments in partition trees

This page was built for publication: Partitioning point sets in arbitrary dimension

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