Algorithm for reporting all triangles with unique interior point

Question

What is known about the complexity of and/or practical algorithms for reporting all triplets of points from finite set of at least four points of which no three are collinear in the Euclidean plane, that define a triangle that contains exactly one point from the set in its interior, i.e. whose barycentric coordinates are strictly positive?

Edit.

after further thinking about the problem, I tend to believe that $O(n^4)$ is the best time complexity possible.

That conclusion comes from the observation, that the inner point $D$ is adjacent to three empty triangles $\Delta_{ABD},\,\Delta_{BCD},\Delta_{CAD}$ and the lower bound for enumerating all empty triangles can be done in $O(n^3)$ as described in Searching for Empty Convex Polygons; in that algorithm a starshaped polygon $P^*_D$ is described, whose edges are visible from a given point $D$ that shall in this question be the inner point of otherwise empty triangles.

The problem of reporting all triangles with unique interior point $D$ would then amount to reporting all directed triangles with their open arcs inside $P^*_D$; the directed graph that contains those triangles corresponds to the visibility graph of $P^*_D$ with arcs corresponding to edges oriented to render $D$ to their left.

Beating the $O(n^4)$ conjectured lower bound would require a sublinear-time algorithm for reporting all directed triangles in an oriented visibility graph of a star-shaped polygon, which doubt is possible.

elaborating on the partitioning idea that Joseph O'Rourke sketched in his comment and combining it with utilizing empty triangles $\Delta_{ABD}$ to identify candidate points $C$ that could define a triangle $\Delta_{ABC}$ with unique innr point $D$, one finds that all solid points outside the shaded empty triangle qualify:

From the picture it can be clearly seen that the set of solid points contains all points that augment the shaded empty triangle to one with unique interior point.

Answer 1

If one arranges $n+1$ points as illustrated below, then there are $n^3/9 = \Omega(n^3)$ triangles each of which includes exactly one point in its interior. So no algorithm can beat $O(n^3)$ in the worst case.

---

         
          ^{Triangles with corners in sets $A,B,C$ include the centerpoint.}

---

Answer 2

Given any two points $p$ and $q$, consider the points above line $pq$. You want to list all points $r$ such that $pqr$ contains exactly one additional point. To do so, sort the points radially around $p$ and around $q$. For each $r$, the points that are contained by $pqr$ are the ones that are (strictly) later than $r$ in the $p$-order, and earlier than $r$ in the $q$-order. Or, if we use position in the two orderings as Cartesian coordinates (with tied points being given equal positions), it's the number of points in the quadrant below and to the left of $r$.

So, for these Cartesian points, compute the lower left frontier (the points with nothing strictly below and left of them) and the second frontier behind that (the points with only lower left frontier points strictly below and left of them). These are standard computations that can be done in time $O(n\log n)$. Only the second frontier points can defined the triangles you're looking for: first frontier points have nothing interior to their triangles and points beyond the second frontier contain at least two points (at least one from each of the first two frontiers). For each second frontier point, binary search to find the range of first-frontier points contained in its quadrant, and return the ones where this range consists of exactly one point.

Repeating this for all $p$ and $q$ gives $O(n^3\log n)$. You can get rid of the logs on the frontier calculations by re-using the cyclic orderings around each point rather than separately computing them for each $(p,q)$ pair, and replace the binary searches by two merge computations on the two frontiers (one to find the left end of each range and another to find the right) to reduce this to $O(n^3)$. And, as you've already determined, the output size can be $\Omega(n^3)$.