A space-optimal solution of general region location
Edelsbrunner H, Maurer H. 1981. A space-optimal solution of general region location. Theoretical Computer Science. 16(3), 329–336.
Journal Article
| Published
| English
Scopus indexed
Author
Edelsbrunner, HerbertISTA 
;
Maurer, Hermann
;
Maurer, HermannAbstract
In 1979 Kirpatrick obtained a practically feasible algorithm for planar regionlocation working in linear space and logarithmic time, provided the regions are bounded by straight line segments. No algorithm requiring only linear space and log-polynomial time was known, so far, for general planar regionlocation, i.e. for the case where regions are bounded by curves more complicated than straight line segments. As main result of this paper such an algorithm is presented.
Publishing Year
Date Published
1981-01-01
Journal Title
Theoretical Computer Science
Volume
16
Issue
3
Page
329 - 336
ISSN
IST-REx-ID
Cite this
Edelsbrunner H, Maurer H. A space-optimal solution of general region location. Theoretical Computer Science. 1981;16(3):329-336. doi:10.1016/0304-3975(81)90103-1
Edelsbrunner, H., & Maurer, H. (1981). A space-optimal solution of general region location. Theoretical Computer Science. Elsevier. https://doi.org/10.1016/0304-3975(81)90103-1
Edelsbrunner, Herbert, and Hermann Maurer. “A Space-Optimal Solution of General Region Location.” Theoretical Computer Science. Elsevier, 1981. https://doi.org/10.1016/0304-3975(81)90103-1.
H. Edelsbrunner and H. Maurer, “A space-optimal solution of general region location,” Theoretical Computer Science, vol. 16, no. 3. Elsevier, pp. 329–336, 1981.
Edelsbrunner H, Maurer H. 1981. A space-optimal solution of general region location. Theoretical Computer Science. 16(3), 329–336.
Edelsbrunner, Herbert, and Hermann Maurer. “A Space-Optimal Solution of General Region Location.” Theoretical Computer Science, vol. 16, no. 3, Elsevier, 1981, pp. 329–36, doi:10.1016/0304-3975(81)90103-1.
All files available under the following license(s):
Copyright Statement:
This Item is protected by copyright and/or related rights. [...]
Link(s) to Main File(s)
Access Level
Open Access
Google Scholar