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?
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 RivinNov 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'RourkeNov 9, 2011 at 16:04
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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).
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.
answered Nov 9, 2011 at 15:29