ETH Zürich /Computer Science /Publications
Search
|
|
Deutsche Version ETH Zürich /Computer Science /Publications Search |
Gabriele Neyer and Frank Wagner, Institute of Theoretical Computer Science, ETH Zürich
| Keywords: | Map labeling Street 2SAT |
|---|---|
| Language: | English |
| Pages: | 18 |
| Available Files: | abstract plain Postscript gnu-compressed PS |
| Abstract: |
American cities, especially their central regions usually have a
very regular street pattern:
We are given a rectangular grid of streets, each street has to be
labeled with a name running along its street, such that no two
labels overlap. For this restricted but yet realistic case an
efficient algorithmic solution for the generally hard labeling problem gets in
reach. The main contribution of this paper is an algorithm that guarantees to solve every solvable instance. So far we are not able to provide a runtime analysis that guarantees efficiency, but the empirical behavior is polynomial without a single exception. The complexity status of the problem is open, we show that a slight generalization, namely the labeling of a cylinder shaped downtown, is NP-hard. Finally, we present efficient algorithms for three special cases including the case of having no labels that are more than half the length of their street. |
May . 1999
|
Comments to
webmaster@inf.ethz.ch
© Department of Computer Science Dynamically generated |
|