| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 430910 | Journal of Discrete Algorithms | 2008 | 9 Pages |
Abstract
We present a fixed-parameter algorithm for the Minimum Convex Partition and the Minimum Weight Convex Partition problem. The algorithm is based on techniques developed for the Minimum Weight Triangulation problem. On a set P of n points the algorithm runs in O(k2k4n3+nlogn)O(2kk4n3+nlogn) time. The parameter k is the number of points in P lying in the interior of the convex hull of P.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Andreas Spillner,