Because the space is bounded and discrete, you can further optimize by triangulating smartly. If you always pick a triangulation point on the boundary, you will

Because the space is bounded and discrete, you can further optimize by triangulating smartly. If you always pick a triangulation point on the boundary, you will always end up with a single candidate as the other candidate will be out of bounds. (Due to discreteness, you can only pick a point near the boundary, but this will still work in a vast majority of cases.) That reduces the average to ~4.