File Download
  • No File Attached
 
Links for fulltext
(May Require Subscription)
 
Supplementary

Article: Randomly generating triangulations of a simple polygon
  • Basic View
  • Metadata View
  • XML View
TitleRandomly generating triangulations of a simple polygon
 
AuthorsDing, Q2
Qian, J3
Tsang, W1
Wang, C3
 
KeywordsAlgorithms
Random processes
Edges
Polygon
Triangulated polygons
 
Issue Date2005
 
PublisherSpringer Verlag.
 
CitationLecture 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.
 
DescriptionProceedings of the Conference on Functional Programming Languages and Computer Architecture
 
ISSN0302-9743
2012 SCImago Journal Rankings: 0.332
 
DC FieldValue
dc.contributor.authorDing, Q
 
dc.contributor.authorQian, J
 
dc.contributor.authorTsang, W
 
dc.contributor.authorWang, C
 
dc.date.accessioned2010-09-06T09:50:40Z
 
dc.date.available2010-09-06T09:50:40Z
 
dc.date.issued2005
 
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.description.naturelink_to_subscribed_fulltext
 
dc.descriptionProceedings of the Conference on Functional Programming Languages and Computer Architecture
 
dc.identifier.citationLecture Notes in Computer Science, 2005, v. 3595, p. 471-480 [How to Cite?]
 
dc.identifier.epage480
 
dc.identifier.hkuros123072
 
dc.identifier.hkuros103538
 
dc.identifier.issn0302-9743
2012 SCImago Journal Rankings: 0.332
 
dc.identifier.openurl
 
dc.identifier.scopuseid_2-s2.0-26844550480
 
dc.identifier.spage471
 
dc.identifier.urihttp://hdl.handle.net/10722/88962
 
dc.identifier.volume3595
 
dc.languageeng
 
dc.publisherSpringer Verlag.
 
dc.relation.ispartofLecture Notes in Computer Science
 
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 polygon
 
dc.typeArticle
 
<?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.  &#169; 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&amp;issn=0302-9743&amp;volume=3595&amp;spage=471&amp;epage=480&amp;date=2005&amp;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
  1. The University of Hong Kong
  2. Zhejiang Radio and TV Transmission Center
  3. Memorial University of Newfoundland