---
_id: '18576'
abstract:
- lang: eng
text: 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:
- first_name: Christian
full_name: Sohler, Christian
last_name: Sohler
citation:
ama: 'Sohler C. Generating Random Star-Shaped Polygons. In: Proceedings of the
11th Canadian Conference on Computational Geometry (''CCCG’99). ; 1999:174-177.'
apa: Sohler, C. (1999). Generating Random Star-Shaped Polygons. In Proceedings
of the 11th Canadian Conference on Computational Geometry ('CCCG’99) (pp.
174–177).
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.
short: 'C. Sohler, in: Proceedings of the 11th Canadian Conference on Computational
Geometry (''CCCG’99), 1999, pp. 174–177.'
date_created: 2020-08-28T14:20:42Z
date_updated: 2022-01-06T06:53:40Z
department:
- _id: '63'
language:
- iso: eng
page: 174-177
publication: Proceedings of the 11th Canadian Conference on Computational Geometry
('CCCG'99)
status: public
title: Generating Random Star-Shaped Polygons
type: conference
user_id: '15415'
year: '1999'
...