> Detailanzeige

Abrahamsen, Mikkel [Verfasser:in]; de Berg, Mark [Verfasser:in]; Buchin, Kevin [Verfasser:in]; Mehr, Mehran [Verfasser:in]; Mehrabi, Ali D. [Verfasser:in] ; Mikkel Abrahamsen and Mark de Berg and Kevin Buchin and Mehran Mehr and Ali D. Mehrabi [Mitwirkende:r]

Minimum Perimeter-Sum Partitions in the Plane

Literatur-
verwaltung

Zur
Merkliste

Lösche von
Merkliste

Per Whatsapp teilen

Schließen

Merkliste



Sie können Bookmarks mittels Listen verwalten, loggen Sie sich dafür bitte in Ihr SLUB Benutzerkonto ein.
  • Medientyp: Sonstige Veröffentlichung; E-Artikel; Elektronischer Konferenzbericht
  • Titel: Minimum Perimeter-Sum Partitions in the Plane
  • Beteiligte: Abrahamsen, Mikkel [Verfasser:in]; de Berg, Mark [Verfasser:in]; Buchin, Kevin [Verfasser:in]; Mehr, Mehran [Verfasser:in]; Mehrabi, Ali D. [Verfasser:in]
  • Erschienen: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017
  • Sprache: Englisch
  • DOI: https://doi.org/10.4230/LIPIcs.SoCG.2017.4
  • Schlagwörter: Computational geometry ; clustering ; convex hull ; minimum-perimeter partition
  • Entstehung:
  • Anmerkungen: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Beschreibung: Let P be a set of n points in the plane. We consider the problem of partitioning P into two subsets P_1 and P_2 such that the sum of the perimeters of CH(P_1) and CH(P_2) is minimized, where CH(P_i) denotes the convex hull of P_i. The problem was first studied by Mitchell and Wynters in 1991 who gave an O(n^2) time algorithm. Despite considerable progress on related problems, no subquadratic time algorithm for this problem was found so far. We present an exact algorithm solving the problem in O(n log^4 n) time and a (1+e)-approximation algorithm running in O(n + 1/e^2 log^4(1/e)) time.
  • Zugangsstatus: Freier Zugang