File Download
There are no files associated with this item.
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Randomly generating triangulations of a simple polygon
Title  Randomly generating triangulations of a simple polygon 

Authors  
Keywords  Algorithms Random processes Edges Polygon Triangulated polygons 
Issue Date  2005 
Publisher  Springer Verlag. 
Citation  Conference on Functional Programming Languages and Computer Architecture. In Lecture Notes in Computer Science, 2005, v. 3595, p. 471480 How to Cite? 
Abstract  In this paper, we present an O(n2+E3/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+E3/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. © SpringerVerlag Berlin Heidelberg 2005. 
Persistent Identifier  http://hdl.handle.net/10722/88962 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
DC Field  Value  Language 

dc.contributor.author  Ding, Q  en_HK 
dc.contributor.author  Qian, J  en_HK 
dc.contributor.author  Tsang, W  en_HK 
dc.contributor.author  Wang, C  en_HK 
dc.date.accessioned  20100906T09:50:40Z   
dc.date.available  20100906T09:50:40Z   
dc.date.issued  2005  en_HK 
dc.identifier.citation  Conference on Functional Programming Languages and Computer Architecture. In Lecture Notes in Computer Science, 2005, v. 3595, p. 471480  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/88962   
dc.description.abstract  In this paper, we present an O(n2+E3/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+E3/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. © SpringerVerlag Berlin Heidelberg 2005.   
dc.language  eng  en_HK 
dc.publisher  Springer Verlag.  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science  en_HK 
dc.rights  The original publication is available at www.springerlink.com   
dc.subject  Algorithms   
dc.subject  Random processes   
dc.subject  Edges   
dc.subject  Polygon   
dc.subject  Triangulated polygons   
dc.title  Randomly generating triangulations of a simple polygon  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.openurl  http://library.hku.hk:4550/resserv?sid=HKU:IR&issn=03029743&volume=3595&spage=471&epage=480&date=2005&atitle=Randomly+generating+triangulations+of+a+simple+polygon  en_HK 
dc.identifier.email  Ding, Q: dingqinh@163.net  en_HK 
dc.identifier.email  Qian, J: jianbo@garfield.cs.mun.ca   
dc.identifier.email  Tsang, W: tsang@cs.hku.hk   
dc.identifier.email  Wang, C: wang@garfield.cs.mun.ca   
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.scopus  eid_2s2.026844550480   
dc.identifier.hkuros  123072  en_HK 
dc.identifier.hkuros  103538   
dc.identifier.volume  3595   
dc.identifier.spage  471   
dc.identifier.epage  480   
dc.identifier.scopusauthorid  Ding, Q=8840441800   
dc.identifier.scopusauthorid  Qian, J=36875721500   
dc.identifier.scopusauthorid  Tsang, W=7201558521   
dc.identifier.scopusauthorid  Wang, C=8895045600   