Show simple item record

dc.contributor.author
Neyer, Gabriele
dc.contributor.author
Wagner, Frank R.
dc.date.accessioned
2017-09-19T06:03:39Z
dc.date.available
2017-06-10T18:21:26Z
dc.date.available
2017-09-19T06:03:39Z
dc.date.issued
1999-05
dc.identifier.uri
http://hdl.handle.net/20.500.11850/68471
dc.identifier.doi
10.3929/ethz-a-009905621
dc.description.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.
en_US
dc.language.iso
en
en_US
dc.publisher
Departement Informatik, ETH Zürich
en_US
dc.rights.uri
http://rightsstatements.org/page/InC-NC/1.0/
dc.subject
CITY MAPS + VILLAGE MAPS
en_US
dc.subject
PROGRAMS AND ALGORITHMS FOR THE SOLUTION OF SPECIAL PROBLEMS
en_US
dc.subject
PROBLEMLÖSEN + PLANEN + SUCHEN (KÜNSTLICHE INTELLIGENZ)
en_US
dc.subject
PROBLEM SOLVING + PLAN GENERATION + SEARCH (ARTIFICIAL INTELLIGENCE)
en_US
dc.subject
STADTPLÄNE + ORTSPLÄNE
en_US
dc.subject
PROGRAMME UND ALGORITHMEN ZUR LÖSUNG SPEZIELLER PROBLEME
en_US
dc.title
Labeling downtown
en_US
dc.type
Report
dc.rights.license
In Copyright - Non-Commercial Use Permitted
dc.date.published
2013
ethz.journal.title
ETH, Eidgenössische Technische Hochschule Zürich, Departement Informatik, Institut für Computersysteme
ethz.journal.volume
324
en_US
ethz.size
11 p.
en_US
ethz.code.ddc
0 - Computer science, information & general works::004 - Data processing, computer science
en_US
ethz.notes
.
en_US
ethz.identifier.nebis
009905621
ethz.publication.place
Zürich
en_US
ethz.publication.status
published
en_US
ethz.leitzahl
ETH Zürich::00002 - ETH Zürich::00012 - Lehre und Forschung::00007 - Departemente::02150 - Dep. Informatik / Dep. of Computer Science
en_US
ethz.date.deposited
2017-06-10T18:22:05Z
ethz.source
ECOL
ethz.source
ECIT
ethz.identifier.importid
imp593650b90cfe915796
ethz.identifier.importid
imp59366b4054e5f60554
ethz.ecolpid
eth:7108
ethz.ecitpid
pub:108685
ethz.eth
yes
en_US
ethz.availability
Open access
en_US
ethz.rosetta.installDate
2017-07-18T23:57:23Z
ethz.rosetta.lastUpdated
2017-09-19T06:03:42Z
ethz.rosetta.versionExported
true
ethz.COinS
ctx_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.atitle=Labeling%20downtown&rft.jtitle=ETH,%20Eidgen%C3%B6ssische%20Technische%20Hochschule%20Z%C3%BCrich,%20Departement%20Informatik,%20Institut%20f%C3%BCr%20Computersysteme&rft.date=1999-05&rft.volume=324&rft.au=Neyer,%20Gabriele&Wagner,%20Frank%20R.&rft.genre=report&
 Search via SFX

Files in this item

Thumbnail

Publication type

Show simple item record