Du är här

A fixed parameter algorithm for the minimum number convex partition problem

Författare:
Publiceringsår: 2004
Språk: Engelska
Sidor: 83-94
Publikation/Tidskrift/Serie: Discrete and Computational Geometry. Japanese Conference, JCDCG 2004. Revised Selected Papers / Lecture Notes in Computer Science
Volym: 3742
Dokumenttyp: Del av eller Kapitel i bok
Förlag: Springer-Verlag

Sammanfattning

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

Disputation

Nyckelord

  • Technology and Engineering
  • 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

Övriga

Published
  • VR 2002-4049
  • ISBN: 3-540-30467-3

Box 117, 221 00 LUND
Telefon 046-222 00 00 (växel)
Telefax 046-222 47 20
lu [at] lu [dot] se

 

Fakturaadress: Box 188, 221 00 LUND
Organisationsnummer: 202100-3211
Om webbplatsen