Webbläsaren som du använder stöds inte av denna webbplats. Alla versioner av Internet Explorer stöds inte längre, av oss eller Microsoft (läs mer här: * https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Var god och använd en modern webbläsare för att ta del av denna webbplats, som t.ex. nyaste versioner av Edge, Chrome, Firefox eller Safari osv.

A fixed parameter algorithm for the minimum number convex partition problem

In English

Författare

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

Avdelning/ar

  • Computer Science

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

Ämne

  • Computer Science

Nyckelord

  • 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

Projekt

  • VR 2002-4049

ISBN/ISSN/Övrigt

  • ISBN: 3-540-30467-3