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 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:
http://lup.lub.lu.se/record/950150
- author
- Grantson Borgelt, Magdalene ^{LU}
- supervisor
- organization
- publishing date
- 2004
- 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 < 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}, title = {Fixed parameter algorithms and other results for convex patitions}, year = {2004}, }