I want to construct the minimal convex hull of some n points such that the hull is a regular polygon of degree n. Math friends, pointers? :)
Conversation
Ah, yes! The last of these in particular seems close…
Basically trying to find minimal circumscribing n-gon
1
for an approximation, you could use Megiddo's algorithm for smallest circle and then circumscribe+shrink an n-gon about that
2
Replying to
Yeah, that's a good strategy! I do know the minimal diameter of the n-gon (it's the diameter of the convex hull), so that helps.
Replying to
Yeah, but diameter of n-gon ≤ diameter of circumcircle (consider equilateral triangle) :(
1
Right, I guess I mean: I know how far to try shrinking! Still seems probably intractable to do at 60 Hz? :/
1
Show replies