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
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
2023 SCImago Journal Rankings: 0.606
References

 

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