Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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 '11 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 '11 at 16:04
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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