
Open access
Datum
1999-05Typ
- Report
ETH Bibliographie
yes
Altmetrics
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. Mehr anzeigen
Persistenter Link
https://doi.org/10.3929/ethz-a-009905621Publikationsstatus
publishedZeitschrift / Serie
ETH, Eidgenössische Technische Hochschule Zürich, Departement Informatik, Institut für ComputersystemeBand
Verlag
Departement Informatik, ETH ZürichThema
CITY MAPS + VILLAGE MAPS; PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS; PROBLEMLÖSEN + PLANEN + SUCHEN (KÜNSTLICHE INTELLIGENZ); PROBLEM SOLVING + PLAN GENERATION + SEARCH (ARTIFICIAL INTELLIGENCE); STADTPLÄNE + ORTSPLÄNE; PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEMEOrganisationseinheit
02150 - Dep. Informatik / Dep. of Computer Science
ETH Bibliographie
yes
Altmetrics