Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Tight time bounds for the minimum local convex partition problem

Grantson Borgelt, Magdalene LU and Levcopoulos, Christos LU orcid (2004) 3742. p.95-105
Abstract
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
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
linear time approximation algorithm, lower time bound, optimal algorithm, edge partition, minimum local convex partition problem, unsorted edges, tight time bound
host publication
Discrete and Computational Geometry. Japanese Conference, JCDCG 2004. Revised Selected Papers / Lecture Notes in Computer Science)
volume
3742
pages
95 - 105
publisher
Springer
external identifiers
  • scopus:33646529193
ISBN
3-540-30467-3
DOI
10.1007/11589440_10
project
VR 2002-4049
language
English
LU publication?
yes
id
62bdf588-c9be-4d80-a4dc-aad7d66a43ca (old id 615176)
date added to LUP
2016-04-04 12:05:13
date last changed
2022-01-29 22:52:40
@inbook{62bdf588-c9be-4d80-a4dc-aad7d66a43ca,
  abstract     = {{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}},
  author       = {{Grantson Borgelt, Magdalene and Levcopoulos, Christos}},
  booktitle    = {{Discrete and Computational Geometry. Japanese Conference, JCDCG 2004. Revised Selected Papers / Lecture Notes in Computer Science)}},
  isbn         = {{3-540-30467-3}},
  keywords     = {{linear time approximation algorithm; lower time bound; optimal algorithm; edge partition; minimum local convex partition problem; unsorted edges; tight time bound}},
  language     = {{eng}},
  pages        = {{95--105}},
  publisher    = {{Springer}},
  title        = {{Tight time bounds for the minimum local convex partition problem}},
  url          = {{http://dx.doi.org/10.1007/11589440_10}},
  doi          = {{10.1007/11589440_10}},
  volume       = {{3742}},
  year         = {{2004}},
}