Overview

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.

Full Product Details

9781332175925

Table of Contents

Reviews

Author Information

Tab Content 6

Customer Reviews

Recent Reviews

Countries Available