Finding extreme points in three dimensions and solving the post-office problem in the plane (Q1069424)

The paper addresses problems of computational geometry in two- and three- space. It is shown that certain point location problems in the plane (assigning an arbitrary point to a given finite partition of the plane) can be optimally solved through a geometric search procedure in three- space: Out of n points in \({\mathbb{R}}^ 3\), find that which is hit first by a given rotating (or sweeping) plane. For the latter problem a solution procedure is presented here which takes O(n) space and O(log n) time for a single query.