# Open problem garden and a pointed pseudotriangulation problem

At the open problem session today, Bojan Mohar plugged his Open Problem Garden, a wiki for unsolved problems in math. Unsurprisingly, it has a heavy bias towards graph theory, but there is some geometry there too.

The problem I described at the session was one I've already described here, so to make up for that here's one I asked Oswin Aichholzer earlier this week, after he gave a nice talk on finding geometric graphs in which each vertex has an adjacent wide angle. The prototypical example of a graph of this type is a pointed pseudotriangulation, a partition of the convex hull of a point set into polygons each having only three convex angles, such that each vertex has an incident concave angle. Every point set in general position has a pointed pseudotriangulation, as do some arbitrarily large subsets of grids:

However, some point sets in special position do not have pointed pseudotriangulations. If there is a point on an edge of the convex hull, it cannot have an incident angle greater than 180 degrees. And if all points lie on two lines and the crossing point of the two lines is included in the point set and interior to the convex hull (as in a quincunx) then that crossing point again cannot have a concave angle. ~~Are those two types of point set the only ones with no pointed pseudotriangulation?~~

**ETA 7/18:** Oswin and Bettina Speckmann have found a few additional examples of point sets with no pointed pseudotriangulation. If they fit a more general pattern, I don't yet see what it is.