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.

counting the triangles containing a point. So the question is the opposite incounting the points contained in a triangle(and reporting the triangles that contain only one). $\endgroup$ – Manfred Weis Feb 22 '20 at 6:46