Finding extreme-points in 3-dimensions and solving the post-office problem in the plane

H. Edelsbrunner, H. Maurer, Information Processing Letters 21 (1985) 39–47.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
Abstract
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.
Publishing Year
Date Published
1985-07-10
Journal Title
Information Processing Letters
Volume
21
Issue
1
Page
39 - 47
IST-REx-ID

Cite this

Edelsbrunner H, Maurer H. Finding extreme-points in 3-dimensions and solving the post-office problem in the plane. Information Processing Letters. 1985;21(1):39-47. doi:10.1016/0020-0190(85)90107-3
Edelsbrunner, H., & Maurer, H. (1985). Finding extreme-points in 3-dimensions and solving the post-office problem in the plane. Information Processing Letters, 21(1), 39–47. https://doi.org/10.1016/0020-0190(85)90107-3
Edelsbrunner, Herbert, and Hermann Maurer. “Finding Extreme-Points in 3-Dimensions and Solving the Post-Office Problem in the Plane.” Information Processing Letters 21, no. 1 (1985): 39–47. https://doi.org/10.1016/0020-0190(85)90107-3.
H. Edelsbrunner and H. Maurer, “Finding extreme-points in 3-dimensions and solving the post-office problem in the plane,” Information Processing Letters, vol. 21, no. 1, pp. 39–47, 1985.
Edelsbrunner H, Maurer H. 1985. Finding extreme-points in 3-dimensions and solving the post-office problem in the plane. Information Processing Letters. 21(1), 39–47.
Edelsbrunner, Herbert, and Hermann Maurer. “Finding Extreme-Points in 3-Dimensions and Solving the Post-Office Problem in the Plane.” Information Processing Letters, vol. 21, no. 1, Elsevier, 1985, pp. 39–47, doi:10.1016/0020-0190(85)90107-3.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar