---
res:
bibo_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.@eng
bibo_authorlist:
- foaf_Person:
foaf_givenName: Christian
foaf_name: Sohler, Christian
foaf_surname: Sohler
dct_date: 1999^xs_gYear
dct_language: eng
dct_title: Generating Random Star-Shaped Polygons@
...