Finding extreme-points in 3-dimensions and solving the post-office problem in the plane
Edelsbrunner, Herbert
Maurer, Hermann
This paper describes an optimal solution for the following geometric search problem defined for a set P of n points in three dimensions: Given a plane h with all points of P on one side and a line ℓ in h, determine a point of P that is hit first when h is rotated around ℓ. The solution takes O(n) space and O(log n) time for a query. By use of geometric transforms, the post-office problem for a finite set of points in two dimensions and certain two-dimensional point location problems are reduced to the former problem and thus also optimally solved.
Elsevier
1985
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/4111
Edelsbrunner H, Maurer H. Finding extreme-points in 3-dimensions and solving the post-office problem in the plane. <i>Information Processing Letters</i>. 1985;21(1):39-47. doi:<a href="https://doi.org/10.1016/0020-0190(85)90107-3">10.1016/0020-0190(85)90107-3</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1016/0020-0190(85)90107-3
info:eu-repo/semantics/altIdentifier/issn/0020-0190
info:eu-repo/semantics/altIdentifier/issn/1872-6119
info:eu-repo/semantics/closedAccess