@inproceedings{18576, abstract = {{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.

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.}}, author = {{Sohler, Christian}}, booktitle = {{Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG'99)}}, pages = {{174--177}}, title = {{{Generating Random Star-Shaped Polygons}}}, year = {{1999}}, }