Empty pseudo-triangles in point sets Original Research Article

We study empty pseudo-triangles in a set image of image points in the plane, where an empty pseudo-triangle has its vertices at the points of image, and no points of image lie inside. We give bounds on the minimum and maximum number of empty pseudo-triangles. If image lies inside a triangle whose corners must be the convex vertices of the pseudo-triangle, then there can be between image and image empty pseudo-triangles. If the convex vertices of the pseudo-triangle are also chosen from image, this number lies between image and image. If we count only star-shaped pseudo-triangles, the bounds are image and image. We also study optimization problems: minimizing or maximizing the perimeter or the area over all empty pseudo-triangles defined by image. If image lies inside a triangle whose corners must be used, we can solve these problems in image time. In the general case, the running times are image for the maximization problems and image for the minimization problems.