7
$\begingroup$

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|$)

$\endgroup$
3
  • 3
    $\begingroup$ What approaches have you considered so far? $\endgroup$
    – koverman47
    Jul 25, 2018 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, 2018 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, 2018 at 19:07

1 Answer 1

11
$\begingroup$

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.)

$\endgroup$
3
  • 1
    $\begingroup$ That ham sandwich is a more successful scientist than most people $\endgroup$
    – koverman47
    Jul 25, 2018 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$
    – Wei Zhan
    Jul 26, 2018 at 6:39
  • $\begingroup$ I added a sentence to Wikipedia citing the Stojmenovíc paper. Maybe later I will expand that entry further. $\endgroup$ Jul 27, 2018 at 12:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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