KIT | KIT-Bibliothek | Impressum
Open Access Logo
DOI: 10.5445/IR/1000020426

On d-regular Schematization of Embedded Paths

Gemsa, Andreas; Nöllenburg, Martin; Pajor, Thomas; Rutter, Ignaz

In the d-regular path schematization problem we are given an embedded path P (e.g.,a route in a road network) and an integer d. The goal is to find a d-schematized embedding
of P in which the orthogonal order of allvertices in the input is preserved and in which every
edge has a slope that is an integer multiple of 90/d. We show that deciding whether a path can
be d-schematized is NP-hard for any integer d. We further model the problem as a mixed-integer linear program. An experimental evaluation indicates that this approach generates reasonable
route sketches for real-world data.

Zugehörige Institution(en) am KIT Institut für Theoretische Informatik (ITI)
Publikationstyp Forschungsbericht
Jahr 2010
Sprache Englisch
Identifikator ISSN: 2190-4782
URN: urn:nbn:de:swb:90-204265
KITopen ID: 1000020426
Serie Karlsruhe Reports in Informatics (früher: Interner Bericht. Fakultät für Informatik, Karlsruher Institut für Technologie) ; 2010, 21
KIT – Die Forschungsuniversität in der Helmholtz-Gemeinschaft KITopen Landing Page