1
$\begingroup$

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?

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

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .