Tight time bounds for the minimum local convex partition problem
(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:
https://lup.lub.lu.se/record/615176
- author
- Grantson Borgelt, Magdalene LU and Levcopoulos, Christos LU
- organization
- publishing date
- 2004
- 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}}, }