I don't think you can get even a polygon that is not convex, because by construction, you start out with a convex polygon (the whole space) and all areas you're clipping away from that are using lines/half-spaces perpendicular to the line connecting the two points. If you assume a metric space with a symmetric metric respecting the triangle inequality, I have the feeling that you encounter a contradiction fairly quickly, but I haven't written down any formal proof either :)