File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Randomly generating triangulations of a simple polygon

TitleRandomly generating triangulations of a simple polygon
Authors
KeywordsAlgorithms
Random processes
Edges
Polygon
Triangulated polygons
Issue Date2005
PublisherSpringer Verlag.
Citation
Conference on Functional Programming Languages and Computer Architecture. In Lecture Notes in Computer Science, 2005, v. 3595, p. 471-480 How to Cite?
AbstractIn this paper, we present an O(n2+|E|3/2) time algorithm for generating triangulations of a simple polygon at random with uniform distribution, where n and |E| are the number of vertices and diagonal edges in the given polygon, respectively. The current best algorithm takes O(n4) time. We also derive algorithms for computing the expected degree of each vertex, the expected number of ears, the expected number of interior triangles, and the expected height of the corresponding tree in such a triangulated polygon. These results are not known for simple polygon. All these algorithms are dominated by the O(n2+|E|3/2) time triangulation counting algorithm. If the results of the triangulation counting algorithm are given, then the triangulation generating algorithm takes O(n log n) time only. All these algorithms are simple and easy to be implemented. © Springer-Verlag Berlin Heidelberg 2005.
Persistent Identifierhttp://hdl.handle.net/10722/88962
ISSN
2014 SCImago Journal Rankings: 0.339

 

DC FieldValueLanguage
dc.contributor.authorDing, Qen_HK
dc.contributor.authorQian, Jen_HK
dc.contributor.authorTsang, Wen_HK
dc.contributor.authorWang, Cen_HK
dc.date.accessioned2010-09-06T09:50:40Z-
dc.date.available2010-09-06T09:50:40Z-
dc.date.issued2005en_HK
dc.identifier.citationConference on Functional Programming Languages and Computer Architecture. In Lecture Notes in Computer Science, 2005, v. 3595, p. 471-480en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/88962-
dc.description.abstractIn this paper, we present an O(n2+|E|3/2) time algorithm for generating triangulations of a simple polygon at random with uniform distribution, where n and |E| are the number of vertices and diagonal edges in the given polygon, respectively. The current best algorithm takes O(n4) time. We also derive algorithms for computing the expected degree of each vertex, the expected number of ears, the expected number of interior triangles, and the expected height of the corresponding tree in such a triangulated polygon. These results are not known for simple polygon. All these algorithms are dominated by the O(n2+|E|3/2) time triangulation counting algorithm. If the results of the triangulation counting algorithm are given, then the triangulation generating algorithm takes O(n log n) time only. All these algorithms are simple and easy to be implemented. © Springer-Verlag Berlin Heidelberg 2005.-
dc.languageengen_HK
dc.publisherSpringer Verlag.en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectAlgorithms-
dc.subjectRandom processes-
dc.subjectEdges-
dc.subjectPolygon-
dc.subjectTriangulated polygons-
dc.titleRandomly generating triangulations of a simple polygonen_HK
dc.typeConference_Paperen_HK
dc.identifier.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0302-9743&volume=3595&spage=471&epage=480&date=2005&atitle=Randomly+generating+triangulations+of+a+simple+polygonen_HK
dc.identifier.emailDing, Q: dingqinh@163.neten_HK
dc.identifier.emailQian, J: jianbo@garfield.cs.mun.ca-
dc.identifier.emailTsang, W: tsang@cs.hku.hk-
dc.identifier.emailWang, C: wang@garfield.cs.mun.ca-
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.scopuseid_2-s2.0-26844550480-
dc.identifier.hkuros123072en_HK
dc.identifier.hkuros103538-
dc.identifier.volume3595-
dc.identifier.spage471-
dc.identifier.epage480-
dc.identifier.scopusauthoridDing, Q=8840441800-
dc.identifier.scopusauthoridQian, J=36875721500-
dc.identifier.scopusauthoridTsang, W=7201558521-
dc.identifier.scopusauthoridWang, C=8895045600-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats