[{"type":"conference","publication":"Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG'99)","department":[{"_id":"63","tree":[{"_id":"7"},{"_id":"34"},{"_id":"44"},{"_id":"43"}]}],"language":[{}],"abstract":[{"lang":"eng"}],"citation":{"bibtex":"@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} }","chicago":"Sohler, Christian. “Generating Random Star-Shaped Polygons.” In Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99), 174–77, 1999.","ieee":"C. Sohler, “Generating Random Star-Shaped Polygons,” in Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99), 1999, pp. 174–177.","mla":"Sohler, Christian. “Generating Random Star-Shaped Polygons.” Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99), 1999, pp. 174–77.","apa":"Sohler, C. (1999). Generating Random Star-Shaped Polygons. In Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99) (pp. 174–177).","short":"C. Sohler, in: Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99), 1999, pp. 174–177."},"user_id":"15415","date_created":"2020-08-28T14:20:42Z","page":"174-177","uri_base":"https://ris.uni-paderborn.de","dc":{"identifier":["https://ris.uni-paderborn.de/record/18576"],"creator":["Sohler, Christian"],"title":["Generating Random Star-Shaped Polygons"],"description":["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."],"rights":["info:eu-repo/semantics/closedAccess"],"source":["Sohler C. Generating Random Star-Shaped Polygons. In: Proceedings of the 11th Canadian Conference on Computational Geometry ('CCCG’99). ; 1999:174-177."],"language":["eng"],"type":["info:eu-repo/semantics/conferenceObject","doc-type:conferenceObject","text","http://purl.org/coar/resource_type/c_5794"],"date":["1999"]},"date_updated":"2022-01-06T06:53:40Z","creator":{"login":"koala","id":"15415"},"_id":"18576","dini_type":"doc-type:conferenceObject","author":[{"last_name":"Sohler","first_name":"Christian"}],"status":"public","message":" #HNIID-1530"}]