Advanced

Fixed parameter algorithms and other results for convex patitions

Grantson Borgelt, Magdalene LU (2004)
Abstract
It is known that the minimum edge length convex partition MWCP of polygons with holes (an example of a PSLG) is NP-hard. Partitioning polygons with holes into the minimum

number of convex polygons MNCP is also known to be NP-hard. We show that The MWCP and MNCP problem for general PSLGs where the sum of the hole vertices and re ex vertices inside the convex hull is sub-logarithmic can be solved in polynomial time. In particular we provide algorithms such that:

1. For any convex polygon P with n perimeter vertices and k hole vertices, the MNCP problem can be solved within the following time bounds:

{ For any constant k, it can be solved in linear time.

{ For k = O( log n log log n), it can be solved in... (More)
It is known that the minimum edge length convex partition MWCP of polygons with holes (an example of a PSLG) is NP-hard. Partitioning polygons with holes into the minimum

number of convex polygons MNCP is also known to be NP-hard. We show that The MWCP and MNCP problem for general PSLGs where the sum of the hole vertices and re ex vertices inside the convex hull is sub-logarithmic can be solved in polynomial time. In particular we provide algorithms such that:

1. For any convex polygon P with n perimeter vertices and k hole vertices, the MNCP problem can be solved within the following time bounds:

{ For any constant k, it can be solved in linear time.

{ For k = O( log n log log n), it can be solved in time polynomial in n. That is O(n k6k5 < 216k) time.

2. For any convex polygon P with n perimeter vertices and k hole vertices, the MWCP problem can be solved within the following time bounds:

{ For any constant k, it can be solved in O(n3) time.

{ For k = O( log n

log log n) it can be solved in time polynomial in n. That is

O(n3

< k4k8

< 213k) time.

{ For k = 2 it can be solved in O(n2) time. (We apply techniques used to

solve the MLCP problem mentioned below.)

3. A special case of the MWCP problem is a polygon with a single hole vertex v.

We will refer to this problem as the minimum local convex partition (MLCP)

problem. We give a MLCP optimal algorithm solving the problem in linear

time if the n edges incident to v are sorted in clockwise order. For unsorted n

incident edges, we provide an

(n log n) lower time bound. A generalized case

is when we need to insert edges of minimum total length in order to remove

concavity around one specialized vertex.

The minimum weight triangulation(MWT) of an MWCP of a polygon P is at most

O(n) longer than its MWT if collinearity of two or more edges is allowed and (log n)

if otherwise. We also show some other related results. (Less)
Please use this url to cite or link to this publication:
author
supervisor
organization
publishing date
type
Thesis
publication status
published
subject
language
English
LU publication?
yes
id
5e8b1df6-9289-467e-b21c-25d2f1479244 (old id 950150)
date added to LUP
2008-01-24 10:54:53
date last changed
2016-09-19 08:45:19
@misc{5e8b1df6-9289-467e-b21c-25d2f1479244,
  abstract     = {It is known that the minimum edge length convex partition MWCP of polygons with holes (an example of a PSLG) is NP-hard. Partitioning polygons with holes into the minimum<br/><br>
number of convex polygons MNCP is also known to be NP-hard. We show that The MWCP and MNCP problem for general PSLGs where the sum of the hole vertices and re ex vertices inside the convex hull is sub-logarithmic can be solved in polynomial time. In particular we provide algorithms such that:<br/><br>
1. For any convex polygon P with n perimeter vertices and k hole vertices, the MNCP problem can be solved within the following time bounds:<br/><br>
{ For any constant k, it can be solved in linear time.<br/><br>
{ For k = O( log n log log n), it can be solved in time polynomial in n. That is O(n k6k5 &lt; 216k) time.<br/><br>
2. For any convex polygon P with n perimeter vertices and k hole vertices, the MWCP problem can be solved within the following time bounds:<br/><br>
{ For any constant k, it can be solved in O(n3) time.<br/><br>
{ For k = O( log n<br/><br>
log log n) it can be solved in time polynomial in n. That is<br/><br>
O(n3<br/><br>
&lt; k4k8<br/><br>
&lt; 213k) time.<br/><br>
{ For k = 2 it can be solved in O(n2) time. (We apply techniques used to<br/><br>
solve the MLCP problem mentioned below.)<br/><br>
3. A special case of the MWCP problem is a polygon with a single hole vertex v.<br/><br>
We will refer to this problem as the minimum local convex partition (MLCP)<br/><br>
problem. We give a MLCP optimal algorithm solving the problem in linear<br/><br>
time if the n edges incident to v are sorted in clockwise order. For unsorted n<br/><br>
incident edges, we provide an <br/><br>
(n log n) lower time bound. A generalized case<br/><br>
is when we need to insert edges of minimum total length in order to remove<br/><br>
concavity around one specialized vertex.<br/><br>
 The minimum weight triangulation(MWT) of an MWCP of a polygon P is at most<br/><br>
O(n) longer than its MWT if collinearity of two or more edges is allowed and (log n)<br/><br>
if otherwise. We also show some other related results.},
  author       = {Grantson Borgelt, Magdalene},
  language     = {eng},
  title        = {Fixed parameter algorithms and other results for convex patitions},
  year         = {2004},
}