> Details

Abrahamsen, Mikkel [Author]; de Berg, Mark [Author]; Buchin, Kevin [Author]; Mehr, Mehran [Author]; Mehrabi, Ali D. [Author] ; Mikkel Abrahamsen and Mark de Berg and Kevin Buchin and Mehran Mehr and Ali D. Mehrabi [Contributor]

Minimum Perimeter-Sum Partitions in the Plane

Reference
management

Bookmarks

Remove from
bookmarks

Share this on Whatsapp

Close

Bookmarks



You can manage bookmarks using lists, please log in to your user account for this.
  • Media type: Text; E-Article; Electronic Conference Proceeding
  • Title: Minimum Perimeter-Sum Partitions in the Plane
  • Contributor: Abrahamsen, Mikkel [Author]; de Berg, Mark [Author]; Buchin, Kevin [Author]; Mehr, Mehran [Author]; Mehrabi, Ali D. [Author]
  • Published: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2017
  • Language: English
  • DOI: https://doi.org/10.4230/LIPIcs.SoCG.2017.4
  • Keywords: Computational geometry ; clustering ; convex hull ; minimum-perimeter partition
  • Origination:
  • Footnote: Diese Datenquelle enthält auch Bestandsnachweise, die nicht zu einem Volltext führen.
  • Description: 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.
  • Access State: Open Access