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.

Tight time bounds for the minimum local convex partition problem

In English

Författare

Summary, in English

Let v be a vertex with n edges incident to it, such that the n edges partition an infinitesimally small circle C around v into convex pieces. The minimum local convex partition (MLCP) problem asks for two or three out of the n edges that still partition C into convex pieces and that are of minimum total length. We present an optimal algorithm solving the problem in linear time if the edges incident to v are sorted clockwise by angle. For unsorted edges our algorithm runs in O(n log n) time. For unsorted edges we also give a linear time approximation algorithm and a lower time bound

Avdelning/ar

  • Computer Science

Publiceringsår

2004

Språk

Engelska

Sidor

95-105

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

  • linear time approximation algorithm
  • lower time bound
  • optimal algorithm
  • edge partition
  • minimum local convex partition problem
  • unsorted edges
  • tight time bound

Status

Published

Projekt

  • VR 2002-4049

ISBN/ISSN/Övrigt

  • ISBN: 3-540-30467-3