Advanced

A fixed parameter algorithm for the minimum number convex partition problem

Grantson Borgelt, Magdalene LU and Levcopoulos, Christos LU (2004) In Discrete and Computational Geometry. Japanese Conference, JCDCG 2004. Revised Selected Papers / Lecture Notes in Computer Science 3742. p.83-94
Abstract
Given an input consisting of an n-vertex convex polygon with k hole vertices or an n-vertex planar straight line graph (PSLG) with k holes and/or reflex vertices inside the convex hull, the parameterized minimum number convex partition (MNCP) problem asks for a partition into a minimum number of convex pieces. We give a fixed-parameter tractable algorithm for this problem that runs in the following time complexities: - linear time if k is constant, - time polynomial in n if k = 0(log/log log n), or, to be exact, in O(n
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
fixed-parameter tractable algorithm, convex hull, parameterized minimum number convex partition problem, time complexity, fixed parameter algorithm, n-vertex convex polygon, n-vertex planar straight line graph
in
Discrete and Computational Geometry. Japanese Conference, JCDCG 2004. Revised Selected Papers / Lecture Notes in Computer Science
volume
3742
pages
83 - 94
publisher
Springer
external identifiers
  • Scopus:33646494887
ISBN
3-540-30467-3
DOI
10.1007/11589440_9
project
VR 2002-4049
language
English
LU publication?
yes
id
79cced35-94ed-435d-b551-39e9cd2f5973 (old id 615173)
date added to LUP
2007-11-26 18:51:26
date last changed
2016-10-13 04:44:49
@misc{79cced35-94ed-435d-b551-39e9cd2f5973,
  abstract     = {Given an input consisting of an n-vertex convex polygon with k hole vertices or an n-vertex planar straight line graph (PSLG) with k holes and/or reflex vertices inside the convex hull, the parameterized minimum number convex partition (MNCP) problem asks for a partition into a minimum number of convex pieces. We give a fixed-parameter tractable algorithm for this problem that runs in the following time complexities: - linear time if k is constant, - time polynomial in n if k = 0(log/log log n), or, to be exact, in O(n},
  author       = {Grantson Borgelt, Magdalene and Levcopoulos, Christos},
  isbn         = {3-540-30467-3},
  keyword      = {fixed-parameter tractable algorithm,convex hull,parameterized minimum number convex partition problem,time complexity,fixed parameter algorithm,n-vertex convex polygon,n-vertex planar straight line graph},
  language     = {eng},
  pages        = {83--94},
  publisher    = {ARRAY(0xbb94098)},
  series       = {Discrete and Computational Geometry. Japanese Conference, JCDCG 2004. Revised Selected Papers / Lecture Notes in Computer Science},
  title        = {A fixed parameter algorithm for the minimum number convex partition problem},
  url          = {http://dx.doi.org/10.1007/11589440_9},
  volume       = {3742},
  year         = {2004},
}