On empty triangles determined by points in the plane (Q1109343)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On empty triangles determined by points in the plane |
scientific article |
Statements
On empty triangles determined by points in the plane (English)
0 references
1988
0 references
Let S be a set of n points in \({\mathbb{R}}^ 2\) in general position such that the convex hull of S is a m-gon. In their first theorem the authors prove that for any such S there exists a set T with at least \(2n-m-2\) points such that the interior of each triangle with vertices in S contains at least one point of S or T. Theorem 2 states that S contains at least (n-1)(n-2)/2 empty triangles, i.e. triangles with vertices in S whose interior does not contain any point of S. The authors construct examples of sets \(S_ n\) such that \(S_ n\) contains at most \(O(n^ 2)\) empty triangles. [Note that S contains \(\left( \begin{matrix} n\\ 3\end{matrix} \right)\) empty triangles if S is the set of vertices of its convex hull.]
0 references
number of triangles
0 references
plane finite set of points
0 references