Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

A fixed parameter algorithm for the minimum number convex partition problem

Grantson Borgelt, Magdalene LU and Levcopoulos, Christos LU orcid (2004) 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
and
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
host publication
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
2016-04-04 11:15:57
date last changed
2022-01-29 21:36:25
@inbook{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}},
  booktitle    = {{Discrete and Computational Geometry. Japanese Conference, JCDCG 2004. Revised Selected Papers / Lecture Notes in Computer Science}},
  isbn         = {{3-540-30467-3}},
  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}},
  language     = {{eng}},
  pages        = {{83--94}},
  publisher    = {{Springer}},
  title        = {{A fixed parameter algorithm for the minimum number convex partition problem}},
  url          = {{http://dx.doi.org/10.1007/11589440_9}},
  doi          = {{10.1007/11589440_9}},
  volume       = {{3742}},
  year         = {{2004}},
}