Generating Random Polygons with Given Vertices
Generating Random Polygons with Given Vertices
复制标题
生成具有给定顶点的随机多边形
DOI：
10.1016/0925-7721(95)00031-3
复制
发表时间：
1996
期刊：
影响因子：
--
通讯作者：
Joseph S. B. Mitchell
中科院分区：
文献类型：
--
作者：
Chong Zhu;Gopalakrishnan Sundaram;J. Snoeyink;Joseph S. B. Mitchell
生成“随机”几何对象的问题是由生成几何算法的测试实例的需要所激发的。我们研究的具体问题，生成一个随机的x-单调多边形的n个顶点的给定集合。这里，“随机”是指我们从所有具有给定n个顶点的x单调多边形中随机均匀地选择一个多边形。给出了一个在O（n）时间和空间内生成随机单调多边形的算法，其中n < K <n2是给定顶点集的x-单调链的可见图的边数.我们还给出了一个O（n3）时间算法生成一个随机凸多边形的顶点是一个给定的一组n点的子集。最后，我们讨论了一些进一步的扩展，以及具有挑战性的开放问题生成随机简单多边形。
The problem of generating “random” geometric objects is motivated by the need to generate test instances for geometric algorithms. We examine the specific problem of generating a random x-monotone polygon on a given set of n vertices. Here, “random” is taken to mean that we select uniformly at random a polygon, from among all those x-monotone polygons having the given n vertices. We give an algorithm that generates a random monotone polygon in O(n) time and space after O(K) preprocessing time, where n < K < n2is the number of edges of the visibility graph of the x-monotone chain of the given vertex set. We also give an O(n3) time algorithm for generating a random convex polygon whose vertices are a subset of a given set of n points. Finally, we discuss some further extensions, as well as the challenging open problem of generating random simple polygons.