conference paper
Generating Random Star-Shaped Polygons
Christian
Sohler
author
63
department
In this paper we deal with two problems on star-shaped polygons. First, we present a Las-Vegas algorithm that uniformly at random creates a star-shaped polygon whose vertices are given by a point set ( S ) of ( n ) points in the plane that does not admit degenerate star-shaped polygons. The expected running time of the algorithm is ( O(n^2log n) ) and it uses ( O(n) ) memory. We call a star-shaped polygon degenerate if its kernel has 0 area.<br><br>Secondly, we show how to count all star-shaped polygons whose vertices are a subset of ( S ) in ( O(n^5log n) ) time and ( O(n) ) space. The algorithm can also be used for random uniform generation. We also present lower and upper bounds on the number of star-shaped polygons.
1999
eng
Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG'99)
174-177
C. Sohler, in: Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99), 1999, pp. 174–177.
Sohler, Christian. “Generating Random Star-Shaped Polygons.” <i>Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99)</i>, 1999, pp. 174–77.
Sohler C. Generating Random Star-Shaped Polygons. In: <i>Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99)</i>. ; 1999:174-177.
C. Sohler, “Generating Random Star-Shaped Polygons,” in <i>Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99)</i>, 1999, pp. 174–177.
Sohler, C. (1999). Generating Random Star-Shaped Polygons. In <i>Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99)</i> (pp. 174–177).
@inproceedings{Sohler_1999, title={Generating Random Star-Shaped Polygons}, booktitle={Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99)}, author={Sohler, Christian}, year={1999}, pages={174–177} }
Sohler, Christian. “Generating Random Star-Shaped Polygons.” In <i>Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99)</i>, 174–77, 1999.
185762020-08-28T14:20:42Z2020-08-28T14:21:07Z