Elias Koutsoupias
Professor of Computer Science
University of Athens
Panepistimiopolis, Ilissia
Athens 15784
Greece

phone: +30 210 7275122
fax: +30 210 7275114

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},