Synopses & Reviews
Synopsis
Excerpt from Partitioning Point Sets in Arbitrary Dimension
Recently A. Yao and F. Yao yy] showed that there exists a partition in d dimensions, for any d. Their partition divides the space into 2 regions, using parts of 3 - 1 planes, so that each of the open regions in the partition contains at most of the points. We show a similar result for the parallel planes partition: it divides the space into 24 regions, using parts of planes, so that each of the Open regions in the partition contains at most of the points. This is a generalization of the partition described in c1]. It is not a variant of the partition given in yy]; the underlying ideas are similar, however.
Both these partitions immediately yield a linear sized data structure for the half-space retrieval problem in d dimensions, supporting a sublinear query time. (the parallel planes partition yields a slightly worse query time than the partition in Further applications of the partition result include the circle retrieval problem y1] and other query problems d132]. Our work and yy] extend these results to arbitrary dimension; for example, both partitions provide a data structure for the sphere retrieval problem supporting a sublinear query time, in arbitrary dimension.
An interesting aspect of our work is that the partition is not by d planes (in fact it uses parts of planes). So the result proved by Avis does not rule out our construction. This Opens up the prospect of finding other partitions for point sets in arbitrary dimension. In fact, it suggests one might seek other partitions enjoying the following properties.
About the Publisher
Forgotten Books publishes hundreds of thousands of rare and classic books. Find more at www.forgottenbooks.com
This book is a reproduction of an important historical work. Forgotten Books uses state-of-the-art technology to digitally reconstruct the work, preserving the original format whilst repairing imperfections present in the aged copy. In rare cases, an imperfection in the original, such as a blemish or missing page, may be replicated in our edition. We do, however, repair the vast majority of imperfections successfully; any imperfections that remain are intentionally left to preserve the state of such historical works.