Algorithm of cutting a polygon into equal parts

Question

I have a convex polygon. I need to divide it into 4 equal parts using the two slit. For example, if I have a square, I have to cut it along the diagonals. Are there some common algorithm for this action?

Answer 1

You can cut the polygon in half by triangulating it with diagonals from a fixed vertex, and then finding the triangle where the area to the left of it is less than half the total area and the area to the right of it is greater than half the total area and finally computing the halving cut from the fixed vertex.

This gives you two convex polygons with the same area. Now you can apply one of the algorithms described in the papers below:

• I. Stojmenovic, Bisections and ham-sandwich cuts of convex polygons and polyhedra, Information Processing Letters, 38, 1 (1991) 15-21.

• B. Armbruster, Finding 2d ham sandwich cuts in linear time.

For the first step, see also

• Thomas C. Shermer, A linear algorithm for bisecting a polygon, Information Processing Letters, 41, 3 (1992) 135-140.

Answer 2

If $P$ is a polygon it is possible to find a line parallel to any fixed direction which divides $P$ in two region of any given area (of course not larger than the area of $P$).

Suppose that the line is vertical (otherwise you can rotate the polygon or adapt the algorithm). Let $p_1=q_1=(x_1,y_1)$ be the vertex of $P$ which has least possible first coordinate $x_1$. Then enumerate the upper and lower vertices starting from $p_1$ by increasing first coordinate: $p_1,p_2,\dots$ are the upper part of the boundary, $q_1,q_2,\dots$ are the lower part of the boundary. Now consider all vertical lines passing through these points and compute the intersection with the edges on the other side of the polygon. For example suppose that between $p_2$ and $q_2$ the point which is left-most is $p_1$. Then you can find a point on the segment $q_1 q_2$ such that it has the same first coordinate of $p_2$. Adding such points, you may assume that the points $p_k$ and $q_k$ have the same $x$-coordinate.

Now you have subdivided your polygon into a finite union of trapezoids with vertical bases. Finding the area of such trapezoids is very easy. So if you want to find a cut with given area, you pass along these trapezoids until you pass the target area. Then you must divide the last trapezoid with a vertical line, so to get the correct total area. Again this is very simple since the area of the trapezoid is a linear function of the $x$ coordinate of the vertical cutting line.

addendum: Notice that the algorithm, as described, can fail if the polygon is not convex.