Draining a Polygon - or - Rolling a Ball out of a Polygon
Draining a Polygon - or - Rolling a Ball out of a Polygon
复制标题
排空多边形 - 或 - 将球滚出多边形
DOI：
10.1016/j.comgeo.2009.08.002
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
J. O'Rourke
中科院分区：
文献类型：
--
作者：
G. Aloupis;J. Cardinal;Sébastien Collette;F. Hurtado;S. Langerman;J. O'Rourke
我们介绍的问题排水（或球代表水滴）穿刺多边形（或多面体）的形状旋转。对于2D多边形，我们得到的组合界限所需的孔的数量，任意多边形和特殊类的多边形。我们详细介绍了一个O（n 2 log n）的算法，找到一个给定的多边形所需的孔的最小数量，并认为复杂性仍然是多项式多面体在3D。我们从描述1-drainable形状开始，这些形状只需要一个孔。
We introduce the problem of draining water (or balls representing water drops) out of a punctured polygon (or a polyhedron) by rotating the shape. For 2D polygons, we obtain combinatorial bounds on the number of holes needed, both for arbitrary polygons and for special classes of polygons. We detail an O (n 2 log n) algorithm that finds the minimum number of holes needed for a given polygon, and argue that the complexity remains polynomial for polyhedra in 3D. We make a start at characterizing the 1-drainable shapes, those that only need one hole.