论文标题
多边形的凸度和预期距离
Degree of Convexity and Expected Distances in Polygons
论文作者
论文摘要
我们提出了一种用于计算$ o（n^2）$ time的Polygon $ p $的所谓啤酒指数的算法，其中$ n $是角落的数量。多边形$ P $可能有孔。啤酒指数是在$ p $中独立和均匀地选择两个点可以彼此看到的两个点的可能性。鉴于有限的$ m $ $ m $ $ m $点在一个简单的多边形$ p $中，我们还展示了如何以$ o（n \ log n+n+m^{4/3} \ log^log^αm\ log n）$ n）$ n）$ n）$ n）$时间来计算彼此进行计算的对数。 同样，我们研究了在简单的多边形$ p $中独立和均匀选择的两个点之间计算两个点之间的预期测地距离的问题。我们展示了如何通过概念上非常简单的算法以最佳$ o（n）$时间计算预期的$ l_1 $ distance。然后，我们描述了一种算法，该算法在$ o（n^2）$ time中输出预期$ l_2 $ distance的封闭式表达式。
We present an algorithm for computing the so-called Beer-index of a polygon $P$ in $O(n^2)$ time, where $n$ is the number of corners. The polygon $P$ may have holes. The Beer-index is the probability that two points chosen independently and uniformly at random in $P$ can see each other. Given a finite set $M$ of $m$ points in a simple polygon $P$, we also show how the number of pairs in $M$ that see each other can be computed in $O(n\log n+m^{4/3}\log^αm\log n)$ time, where $α<1.78$ is a constant. We likewise study the problem of computing the expected geodesic distance between two points chosen independently and uniformly at random in a simple polygon $P$. We show how the expected $L_1$-distance can be computed in optimal $O(n)$ time by a conceptually very simple algorithm. We then describe an algorithm that outputs a closed-form expression for the expected $L_2$-distance in $O(n^2)$ time.
