Suppose, we have two non-overlapping convex polygons $A$ and $B$. How can we draw one straight line which divides $A$ into two parts of equal area and also divides $B$ into two equal area parts? Also, can we do this in complexity $O(n^2)$ or better? ($n = |A| + |B|$)

  • 3
    $\begingroup$ What approaches have you considered so far? $\endgroup$ – koverman47 Jul 25 '18 at 14:59
  • 1
    $\begingroup$ What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Jul 25 '18 at 17:21
  • $\begingroup$ I got stuck in this problem when I was trying to solve this. This is not like homework or anything. Also, I don't have any idea till now about solving it. $\endgroup$ – John Reese Jul 25 '18 at 19:07

This is known as the Ham-Sandwich theorem:

Given two measurable objects in $2$-dimensional Euclidean space, it is possible to divide each of them in half with a line.

Note: Convexity is not needed. And $\mathbb{R}^2$ can be replaced by $\mathbb{R}^d$ with "line" replaced by a $(d{-}1)$-dimensional hyperplane.

          (Image from curiosity.com.)
See the Wikipedia link for computational versions.

Added in response to @WillardZhan's request:

Ivan Stojmenovíc. Bisections and ham-sandwich cuts of convex polygons and polyhedra. Inf. Process. Lett. 38(1): 15-21. 1991. (CiteSeer PDF download.)
Abstract. We present a linear time sequential algorithm for finding a straight line that bisects two given disjoint convex polygons (i.e. cuts both of them into parts of equal area).

Abbott, Timothy G., Erik D. Demaine, Martin L. Demaine, Daniel M. Kane, Stefan Langerman, Jelani Nelson, and Vincent Yeung. "Dynamic Ham-Sandwich Cuts of Convex Polygons in the Plane." In CCCG, pp. 61-64. 2005. (PDF download.)

| cite | improve this answer | |
  • 1
    $\begingroup$ That ham sandwich is a more successful scientist than most people $\endgroup$ – koverman47 Jul 25 '18 at 21:49
  • 2
    $\begingroup$ I'm not sure how the point set version of this problem described in the wikipedia link solves OP's question on polygons. Please elaborate if you will. $\endgroup$ – Willard Zhan Jul 26 '18 at 6:39
  • $\begingroup$ I added a sentence to Wikipedia citing the Stojmenovíc paper. Maybe later I will expand that entry further. $\endgroup$ – Joseph O'Rourke Jul 27 '18 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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