Meny

Javascript is not activated in your browser. This website needs javascript activated to work properly.
Du är här

Tight time bounds for the minimum local convex partition problem

Författare:
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-Verlag

Sammanfattning

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

Disputation

Nyckelord

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

Ö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