E. Koutsoupias, C. H. Papadimitriou, and M. Sideri.

**On the optimal bisection of a polygon.***ORSA Journal on Computing*, 4(4):435--438, Fall 1992.### Abstract

We show that bisecting a polygon into two equal (possibly disconnected) parts with the smallest possible total perimeter is NP-complete, and it is in fact NP-hard to approximate within any ratio.In contrast, we give a dynamic programming algorithm which finds a subdivision into two parts with total perimeter at most that of the optimum bisection, such that the two parts have areas within $\epsilon$ of each other; the time is polynomial in the number of sides of the polygon, and $1\over \epsilon$.When the polygon is convex, or if the parts are required to be connected, then the exact problem can be solved in quadratic time.### Bib

@Article{KPS92, author = {E. Koutsoupias and C. H. Papadimitriou and M. Sideri}, title = {On the optimal bisection of a polygon}, journal = {ORSA Journal on Computing}, year = 1992, month = {Fall}, volume = 4, number = 4, pages = {435--438} } @InProceedings{KPS90, author = {E. Koutsoupias and C. H. Papadimitriou and M. Sideri}, title = {On the optimal bisection of a polygon}, booktitle = {Proceedings of the Sixth Annual Symposium on Computational Geometry}, year = 1990, month = {6--8 } # jun, pages = {198--202}, address = {Berkeley, California}}