Tight time bounds for the minimum local convex partition problem
(2004) In Discrete and Computational Geometry. Japanese Conference, JCDCG 2004. Revised Selected Papers / Lecture Notes in Computer Science) 3742. p.95105 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:
http://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
 in
 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
 3540304673
 DOI
 10.1007/11589440_10
 project
 VR 20024049
 language
 English
 LU publication?
 yes
 id
 62bdf588c9be4d80a4dcaad7d66a43ca (old id 615176)
 date added to LUP
 20071126 18:53:36
 date last changed
 20170101 08:06:51
@inbook{62bdf588c9be4d80a4dcaad7d66a43ca, 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}, isbn = {3540304673}, keyword = {linear time approximation algorithm,lower time bound,optimal algorithm,edge partition,minimum local convex partition problem,unsorted edges,tight time bound}, language = {eng}, pages = {95105}, publisher = {Springer}, series = {Discrete and Computational Geometry. Japanese Conference, JCDCG 2004. Revised Selected Papers / Lecture Notes in Computer Science)}, title = {Tight time bounds for the minimum local convex partition problem}, url = {http://dx.doi.org/10.1007/11589440_10}, volume = {3742}, year = {2004}, }