Empty pseudo-triangles in point sets ?
We study empty pseudo-triangles in a set P P of n n points in the plane, where an empty pseudo-triangle has its vertices at the points of P P , and no points of P P lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If P P lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between ?(n2) ? ( n 2 ) and ?(n3) ? ( n 3 ) empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from P P , this number lies between ?(n3) ? ( n 3 ) and ?(n6) ? ( n 6 ) . If we count only star-shaped pseudo-triangles, the bounds are ?(n2) ? ( n 2 ) and ?(n5) ? ( n 5 ) . We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by P P . If P P lies inside a triangle whose corners must be used, we can solve these problems in O(n3) O ( n 3 ) time. In the general case, the running times are O(n6) O ( n 6 ) for the maximization problems and O(nlogn) O ( n log n ) for the minimization problems.
finite planar point set pseudo-triangle count optimal pseudo-triangle computation