A space-optimal solution of general region location Journal Article


Author(s): Edelsbrunner, Herbert; Maurer, Hermann A
Article Title: A space-optimal solution of general region location
Affiliation
Abstract: 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.
Journal Title: Theoretical Computer Science
Volume: 16
Issue 3
ISSN: 0304-3975
Publisher: Elsevier  
Date Published: 1981-01-01
Start Page: 329
End Page: 336
DOI: 10.1016/0304-3975(81)90103-1
Open access: no
IST Austria Authors
Related IST Austria Work