Speaker: Iris Reinbacher (POSTECH)

Title: Empty Pseudo Triangle in Point Sets

Abstract:
We study empty pseudo-triangles in a set of $n$ points in the plane, where an empty pseudo-triangle has three convex vertices that are connected by concave chains on the given points, such that there are no points in the interior of the pseudo-triangle.

First, we give bounds on the number of possible empty pseudo-triangles. If the three convex vertices are fixed, there can be between $\Theta(n^2)$ and $\Theta(n^3)$ empty pseudo-triangles, whereas, if the convex vertices are not fixed, their number lies between $\Theta(n^3)$ and $\Theta(n^6)$. If we allow only star-shaped pseudo-triangles, the upper bounds reduce by a factor of $n$ in both cases.

Second, we study three optimization problems: minimizing the perimeter, maximizing the area and minimizing the longest concave chain of an empty pseudo-triangle. If the convex vertices are fixed, we can solve all problems in $O(n^3)$ time. If the convex vertices are not given, we achieve running times of $O(n \log n), O(n^6)$, and $O(n\log n)$ time respectively. In any case, we use only linear space.