File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Article: Progress on maximum weight triangulation

TitleProgress on maximum weight triangulation
Authors
Chin, FYLQian, JWang, CA
KeywordsAlgorithm
Approximation
Maximum weight triangulation
Issue Date2004
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3106, p. 53-61 How to Cite?
AbstractIn this paper, we investigate the maximum weight triangulation of a point set in the plane. We prove that the weight of maximum weight triangulation of any planar point set with diameter D is bounded above by ((2ε+2)·n+π(1-2ε)/8ε√1-ε 2+π/2-5(ε+1))D, where ε for 0 < ε ≤ 1/2 is a constant and n is the numb er of points in the set. If we use 'spoke-scan' algorithm to find a triangulation of the point set, we obtain an approximation ratio of 4.238. Furthermore, if the point set forms a 'semi-lune' or a 'semi-circled' convex polygon', then its maximum weight triangulation can be found in O(n2) time. © Springer-Verlag Berlin Heidelberg 2004.
Persistent Identifierhttp://hdl.handle.net/10722/93333
ISSN
0302-9743
2023 SCImago Journal Rankings: 0.606
References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_HK
dc.contributor.authorQian, Jen_HK
dc.contributor.authorWang, CAen_HK
dc.date.accessioned2010-09-25T14:57:55Z-
dc.date.available2010-09-25T14:57:55Z-
dc.date.issued2004en_HK
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2004, v. 3106, p. 53-61en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93333-
dc.description.abstractIn this paper, we investigate the maximum weight triangulation of a point set in the plane. We prove that the weight of maximum weight triangulation of any planar point set with diameter D is bounded above by ((2ε+2)·n+π(1-2ε)/8ε√1-ε 2+π/2-5(ε+1))D, where ε for 0 < ε ≤ 1/2 is a constant and n is the numb er of points in the set. If we use 'spoke-scan' algorithm to find a triangulation of the point set, we obtain an approximation ratio of 4.238. Furthermore, if the point set forms a 'semi-lune' or a 'semi-circled' convex polygon', then its maximum weight triangulation can be found in O(n2) time. © Springer-Verlag Berlin Heidelberg 2004.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_HK
dc.subjectAlgorithmen_HK
dc.subjectApproximationen_HK
dc.subjectMaximum weight triangulationen_HK
dc.titleProgress on maximum weight triangulationen_HK
dc.typeArticleen_HK
dc.identifier.emailChin, FYL:chin@cs.hku.hken_HK
dc.identifier.authorityChin, FYL=rp00105en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-35048873357en_HK
dc.identifier.hkuros91384en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-35048873357&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume3106en_HK
dc.identifier.spage53en_HK
dc.identifier.epage61en_HK
dc.publisher.placeGermanyen_HK
dc.identifier.scopusauthoridChin, FYL=7005101915en_HK
dc.identifier.scopusauthoridQian, J=7402196542en_HK
dc.identifier.scopusauthoridWang, CA=7501646353en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats