Fixed parameter algorithms and other results for convex patitions
(2004) Abstract
 It is known that the minimum edge length convex partition MWCP of polygons with holes (an example of a PSLG) is NPhard. Partitioning polygons with holes into the minimum
number of convex polygons MNCP is also known to be NPhard. 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 sublogarithmic 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 NPhard. Partitioning polygons with holes into the minimum
number of convex polygons MNCP is also known to be NPhard. 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 sublogarithmic 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:
http://lup.lub.lu.se/record/950150
 author
 Grantson Borgelt, Magdalene ^{LU}
 supervisor

 Christos Levcopoulos ^{LU}
 Andrzej Lingas ^{LU}
 organization
 publishing date
 2004
 type
 Thesis
 publication status
 published
 subject
 language
 English
 LU publication?
 yes
 id
 5e8b1df69289467eb21c25d2f1479244 (old id 950150)
 date added to LUP
 20080124 10:54:53
 date last changed
 20181121 21:21:02
@misc{5e8b1df69289467eb21c25d2f1479244, abstract = {It is known that the minimum edge length convex partition MWCP of polygons with holes (an example of a PSLG) is NPhard. Partitioning polygons with holes into the minimum<br/><br> number of convex polygons MNCP is also known to be NPhard. 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 sublogarithmic 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 < 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> < k4k8<br/><br> < 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}, note = {Licentiate Thesis}, title = {Fixed parameter algorithms and other results for convex patitions}, year = {2004}, }