查找所有空三角形 [英] Finding all empty triangles

问题描述

我有一小部分的 N 在平面上的点， N'LT; 50 。

I have a small set of N points in the plane, N < 50.

我想列举要点是对所有从三元形成不包含其他点的三角形设定。

I want to enumerate all triples of points from the set that form a triangle containing no other point.

尽管明显的蛮力解决方案是可行的我的小 N ，它具有复杂性 O（N ^ 4）。

Even though the obvious brute force solution could be viable for my tiny N, it has complexity O(N^4).

你知道一种方法来降低时间复杂度，说 O（N³）或 O（N²）将保持code简单吗？没有图书馆不允许的。

Do you know a way to decrease the time complexity, say to O(N³) or O(N²) that would keep the code simple ? No library allowed.

出乎我的意料，这样的三角形数量为pretty的大。采取任意点为中心，其他的人，通过增加它周围角度进行排序。这形成了一个星形多边形，给出 N-1 空的三角形，因此总的Ω（N²） 。它已经表明，这种结合很​​紧[平面点设置为空凸多边形，一巴拉尼和P. Valtr少数。

Much to my surprise, the number of such triangles is pretty large. Take any point as a center and sort the other ones by increasing angle around it. This forms a star-shaped polygon, that gives N-1 empty triangles, hence a total of Ω(N²). It has been shown that this bound is tight [Planar Point Sets with a Small Number of Empty convex Polygons, I. Bárány and P. Valtr].

在形成一个凸多边形点的情况下，所有三角形都是空的，因此 O（N³）。的快速算法机会是越来越低：（

In the case of points forming a convex polygon, all triangles are empty, hence O(N³). Chances of a fast algorithm are getting low :(

推荐答案

本文搜索空凸多边形由布金，大卫P. / Edelsbrunner，赫伯特/奥维马斯，马克·的包含算法线性中可能的输出的三角形为解决这一问题的数目。

The paper "Searching for empty Convex polygons" by Dobkin, David P. / Edelsbrunner, Herbert / Overmars, Mark H. contains an algorithm linear in the number of possible output triangles for solving this problem.

在计算几何的一个关键问题是具有特殊属性点集合的子集的识别。我们研究这个问题的凸性和空虚的属性。我们表明，发现空三角是相关determininng对顶点看到对方starshaped多边形的问题。线性时间的算法为这个问题，这是独立的利益的产生查找所有空三角形的优化算法。然后，该结果被扩展到一个算法查找   空凸R-边形（R> 3），用于确定最大的空凸子集。最后，扩展到更高的维度被提及。

A key problem in computational geometry is the identification of subsets of a point set having particular properties. We study this problem for the properties of convexity and emptiness. We show that finding empty triangles is related to the problem of determininng pairs of vertices that see each other in starshaped polygon. A linear time algorithm for this problem which is of independent interest yields an optimal algorithm for finding all empty triangles. This result is then extended to an algorithm for finding empty convex r-gons (r > 3) and for determining a largest empty convex subset. Finally, extensions to higher dimensions are mentioned.

这篇关于查找所有空三角形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！