The browser you are using is not supported by this website. All versions of Internet Explorer are no longer supported, either by us or Microsoft (read more here: https://www.microsoft.com/en-us/microsoft-365/windows/end-of-ie-support).

Please use a modern browser to fully experience our website, such as the newest versions of Edge, Chrome, Firefox or Safari etc.

Tight time bounds for the minimum local convex partition problem

På svenska

Author

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

Department/s

  • Computer Science

Publishing year

2004

Language

English

Pages

95-105

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

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

Status

Published

Project

  • VR 2002-4049

ISBN/ISSN/Other

  • ISBN: 3-540-30467-3