A fixed parameter algorithm for the minimum number convex partition problem
Author
Summary, in English
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
Department/s
- Computer Science
Publishing year
2004
Language
English
Pages
83-94
Publication/Series
Discrete and Computational Geometry. Japanese Conference, JCDCG 2004. Revised Selected Papers / Lecture Notes in Computer Science
Volume
3742
Document type
Book chapter
Publisher
Springer
Topic
- Computer Science
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
Status
Published
Project
- VR 2002-4049
ISBN/ISSN/Other
- ISBN: 3-540-30467-3