New answers tagged cg.comp-geom
2
To complement Sariel's answer, some closely related problems are hard. In particular, for a non-convex polygon, it's NP-hard to find a partition into two pieces of equal area while minimizing the length of the cut. See: Elias Koutsoupias, Christos Papadimitriou, and Martha Sideri (1992), "On the optimal bisection of a polygon", ORSA J. Comput. 4 (4)...
2
There must be many ways to do it - here is one way...
Compute the medial axis of the polygon using the $L_1$ metric. Any point on the boundary defines a natural segment that goes from this point to a point on the medial axis - lets call the leash of the point. Pick an arbitrary point on the boundary of the polygon, and start moving it counterclockwise. ...
2
The outline from Marc Lackenby's talk about a quasipolynomial algorithm for Unknottedness.
Unknot recognition in quasipolynomial time outline.. Under the talks section there are slides about the algorithm.
And for the seminar video, which has been uploaded link to the video and more about the result. .
8
Such a quasi-polynomial algorithm has just been claimed by Marc Lackenby from Oxford University. He will present in next Tuesday (02 Feb 2021) in a Zoom talk: https://www.math.ucdavis.edu/research/seminars/?talk_id=6082
Top 50 recent answers are included
