**Article:**Randomly generating triangulations of a simple polygon

Title | Randomly generating triangulations of a simple polygon |
---|---|

Authors | Ding, Q2 Qian, J3 Tsang, W1 Wang, C3 |

Keywords | Algorithms Random processes Edges Polygon Triangulated polygons |

Issue Date | 2005 |

Publisher | Springer Verlag. |

Citation | Lecture Notes in Computer Science, 2005, v. 3595, p. 471-480 [How to Cite?] |

Abstract | In 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. |

Description | Proceedings of the Conference on Functional Programming Languages and Computer Architecture |

ISSN | 0302-9743 2013 SCImago Journal Rankings: 0.310 |

DC Field | Value |
---|---|

dc.contributor.author | Ding, Q |

dc.contributor.author | Qian, J |

dc.contributor.author | Tsang, W |

dc.contributor.author | Wang, C |

dc.date.accessioned | 2010-09-06T09:50:40Z |

dc.date.available | 2010-09-06T09:50:40Z |

dc.date.issued | 2005 |

dc.description.abstract | In 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.description.nature | link_to_subscribed_fulltext |

dc.description | Proceedings of the Conference on Functional Programming Languages and Computer Architecture |

dc.identifier.citation | Lecture Notes in Computer Science, 2005, v. 3595, p. 471-480 [How to Cite?] |

dc.identifier.epage | 480 |

dc.identifier.hkuros | 123072 |

dc.identifier.hkuros | 103538 |

dc.identifier.issn | 0302-9743 2013 SCImago Journal Rankings: 0.310 |

dc.identifier.openurl | |

dc.identifier.scopus | eid_2-s2.0-26844550480 |

dc.identifier.spage | 471 |

dc.identifier.uri | http://hdl.handle.net/10722/88962 |

dc.identifier.volume | 3595 |

dc.language | eng |

dc.publisher | Springer Verlag. |

dc.relation.ispartof | Lecture Notes in Computer Science |

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 |

dc.type | Article |

<?xml encoding="utf-8" version="1.0"?> <item><contributor.author>Ding, Q</contributor.author> <contributor.author>Qian, J</contributor.author> <contributor.author>Tsang, W</contributor.author> <contributor.author>Wang, C</contributor.author> <date.accessioned>2010-09-06T09:50:40Z</date.accessioned> <date.available>2010-09-06T09:50:40Z</date.available> <date.issued>2005</date.issued> <identifier.citation>Lecture Notes in Computer Science, 2005, v. 3595, p. 471-480</identifier.citation> <identifier.issn>0302-9743</identifier.issn> <identifier.uri>http://hdl.handle.net/10722/88962</identifier.uri> <description>Proceedings of the Conference on Functional Programming Languages and Computer Architecture</description> <description.abstract>In 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.</description.abstract> <language>eng</language> <publisher>Springer Verlag.</publisher> <relation.ispartof>Lecture Notes in Computer Science</relation.ispartof> <rights>The original publication is available at www.springerlink.com</rights> <subject>Algorithms</subject> <subject>Random processes</subject> <subject>Edges</subject> <subject>Polygon</subject> <subject>Triangulated polygons</subject> <title>Randomly generating triangulations of a simple polygon</title> <type>Article</type> <identifier.openurl>http://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+polygon</identifier.openurl> <description.nature>link_to_subscribed_fulltext</description.nature> <identifier.scopus>eid_2-s2.0-26844550480</identifier.scopus> <identifier.hkuros>123072</identifier.hkuros> <identifier.hkuros>103538</identifier.hkuros> <identifier.volume>3595</identifier.volume> <identifier.spage>471</identifier.spage> <identifier.epage>480</identifier.epage> </item>

Author Affiliations

- The University of Hong Kong
- Zhejiang Radio and TV Transmission Center
- Memorial University of Newfoundland