1

Dear All,

I have convex polygon (expressed by points in cartesian coordinate system). I am looking for a solution to splitting into two congruent pieces. Is there any way to to estimate the points that lead cut?

flag
I cannot parse the question: what do you mean by splitting? what do you mean by "estimate the points that lead cut"? – Igor Rivin Nov 9 2011 at 15:28
@Igor: My take is that "splitting" means to find a boundary-to-boundary path that "cuts" the polygon into two congruent pieces. – Joseph O'Rourke Nov 9 2011 at 16:04

1 Answer

4

There exist convex quadrilaterals which have no such splitting. And there is an $O(n^3)$ algorithm to decide if such a splitting exists for a (nonconvex) $n$-gon. See the paper by Dania El-Khechen, Thomas Fevens, John Iacono, and Günter Rote, "Partitioning a polygon into two mirror congruent pieces." In Proc. 20th Canad. Conf. Comput. Geom., pages 131-134, August 2008 (PDF download link).
                Fig 1
I am unaware of work specifically on convex polygon partitions, but perhaps if you specialize the algorithm in this paper to that simpler situation, its time complexity will improve.

link|flag

Your Answer

Get an OpenID
or

Not the answer you're looking for? Browse other questions tagged or ask your own question.