File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Approximation of polygonal curves with minimum number of line segments or minimum error

TitleApproximation of polygonal curves with minimum number of line segments or minimum error
Authors
KeywordsPolygonal approximation
Number of line segments
Minimum error
Convex polygonal curves
Issue Date1996
PublisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscinet.com/ijcga/ijcga.shtml
Citation
International Journal of Computational Geometry and Applications, 1996, v. 6 n. 1, p. 59-77 How to Cite?
AbstractWe improve the time complexities for solving the polygonal curve approximation problems formulated by Imai and Iri. The time complexity for approximating any polygonal curve of n vertices with minimum number of line segments can be improved from O(n2log n) to O(n2). The time complexity for approximating any polygonal curve with minimum error can also be improved from O(n2log2n) to O(n2log n). We further show that if the curve to be approximated forms part of a convex polygon, the two problems can be solved in O(n) and O(n2) time respectively for both open and closed polygonal curves.
Persistent Identifierhttp://hdl.handle.net/10722/88918
ISSN
2013 Impact Factor: 0.082
2015 SCImago Journal Rankings: 0.988

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorChan, WSen_HK
dc.date.accessioned2010-09-06T09:50:07Z-
dc.date.available2010-09-06T09:50:07Z-
dc.date.issued1996en_HK
dc.identifier.citationInternational Journal of Computational Geometry and Applications, 1996, v. 6 n. 1, p. 59-77en_HK
dc.identifier.issn0218-1959en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88918-
dc.description.abstractWe improve the time complexities for solving the polygonal curve approximation problems formulated by Imai and Iri. The time complexity for approximating any polygonal curve of n vertices with minimum number of line segments can be improved from O(n2log n) to O(n2). The time complexity for approximating any polygonal curve with minimum error can also be improved from O(n2log2n) to O(n2log n). We further show that if the curve to be approximated forms part of a convex polygon, the two problems can be solved in O(n) and O(n2) time respectively for both open and closed polygonal curves.-
dc.languageengen_HK
dc.publisherWorld Scientific Publishing Co Pte Ltd. The Journal's web site is located at http://www.worldscinet.com/ijcga/ijcga.shtmlen_HK
dc.relation.ispartofInternational Journal of Computational Geometry and Applicationsen_HK
dc.subjectPolygonal approximation-
dc.subjectNumber of line segments-
dc.subjectMinimum error-
dc.subjectConvex polygonal curves-
dc.titleApproximation of polygonal curves with minimum number of line segments or minimum erroren_HK
dc.typeArticleen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0218-1959&volume=6&issue=1&spage=59&epage=77&date=1996&atitle=Approximation+of+polygonal+curves+with+minimum+number+of+line+segments+or+minimum+erroren_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1142/S0218195996000058-
dc.identifier.scopuseid_2-s2.0-0030535803-
dc.identifier.hkuros9910en_HK

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats