SwePub
Sök i LIBRIS databas

  Extended search

WFRF:(Maurer Florian P.)
 

Search: WFRF:(Maurer Florian P.) > (2016) > Computing Nonsimple...

  • 1 of 1
  • Previous record
  • Next record
  •    To hitlist
  • Fekete, Sandor P.TU Braunschweig, Germany (author)

Computing Nonsimple Polygons of Minimum Perimeter

  • Article/chapterEnglish2016

Publisher, publication year, extent ...

  • 2016-06-01
  • Cham :SPRINGER INT PUBLISHING AG,2016
  • printrdacarrier

Numbers

  • LIBRIS-ID:oai:DiVA.org:liu-132697
  • https://urn.kb.se/resolve?urn=urn:nbn:se:liu:diva-132697URI
  • https://doi.org/10.1007/978-3-319-38851-9_10DOI

Supplementary language notes

  • Language:English
  • Summary in:English

Part of subdatabase

Classification

  • Subject category:ref swepub-contenttype
  • Subject category:kon swepub-publicationtype

Notes

  • We provide exact and approximation methods for solving a geometric relaxation of the Traveling Salesman Problem (TSP) that occurs in curve reconstruction: for a given set of vertices in the plane, the problem Minimum Perimeter Polygon (MPP) asks for a (not necessarily simply connected) polygon with shortest possible boundary length. Even though the closely related problem of finding a minimum cycle cover is polynomially solvable by matching techniques, we prove how the topological structure of a polygon leads to NP-hardness of the MPP. On the positive side, we show how to achieve a constant-factor approximation. When trying to solve MPP instances to provable optimality by means of integer programming, an additional difficulty compared to the TSP is the fact that only a subset of subtour constraints is valid, depending not on combinatorics, but on geometry. We overcome this difficulty by establishing and exploiting additional geometric properties. This allows us to reliably solve a wide range of benchmark instances with up to 600 vertices within reasonable time on a standard machine. We also show that using a natural geometry-based sparsification yields results that are on average within 0.5% of the optimum.

Subject headings and genre

Added entries (persons, corporate bodies, meetings, titles ...)

  • Haas, AndreasTU Braunschweig, Germany (author)
  • Hemmer, MichaelTU Braunschweig, Germany (author)
  • Hoffmann, MichaelSwiss Federal Institute Technology, Switzerland (author)
  • Kostitsyna, IrinaTU Eindhoven, Netherlands (author)
  • Krupke, DominikTU Braunschweig, Germany (author)
  • Maurer, FlorianTU Braunschweig, Germany (author)
  • Mitchell, Joseph S. B.SUNY Stony Brook, NY 11794 USA (author)
  • Schmidt, ArneTU Braunschweig, Germany (author)
  • Schmidt, ChristianeLinköpings universitet,Kommunikations- och transportsystem,Tekniska fakulteten(Swepub:liu)chrsc91 (author)
  • Troegel, JulianTU Braunschweig, Germany (author)
  • TU Braunschweig, GermanySwiss Federal Institute Technology, Switzerland (creator_code:org_t)

Related titles

  • In:EXPERIMENTAL ALGORITHMS, SEA 2016Cham : SPRINGER INT PUBLISHING AG, s. 134-14997833193885029783319388519

Internet link

Find in a library

To the university's database

  • 1 of 1
  • Previous record
  • Next record
  •    To hitlist

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Close

Copy and save the link in order to return to this view