Understanding the Ham-Sandwich Theorem in Computational Geometry

The Ham-Sandwich Theorem states that given two finite point sets in the plane, there exists a line that divides each set such that each side contains at most half of the points in that set. The proof involves finding such a line and rotating it to maintain the property. This concept is essential in computational geometry and has practical applications in various fields.

• Computational Geometry
• Ham-Sandwich Theorem
• Point Sets
• Line Division
• Rotation

myk_wal Follow

Uploaded on Nov 17, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. CMPS 3130/6130 Computational Geometry Spring 2020 Ham Sandwich Theorem Carola Wenk 3/31/20 1 CMPS 3130/6130 Computational Geometry

2. Ham-Sandwich Theorem Theorem: Let P and Q be two finite point sets in the plane. Then there exists a line l such that on each side of l there are at most |P|/2 points of P and at most |Q|/2 points of Q. 3/31/20 2 CMPS 3130/6130 Computational Geometry

3. Ham-Sandwich Theorem Proof: Find a line l such that on each side of l there are at most |P|/2 points of P. Then rotate l counter-clockwise in such a way that there are always at most |P|/2 points of P on each side of l. 3/31/20 3 CMPS 3130/6130 Computational Geometry

4. Rotation Left: 4 Right: 4 3/31/20 4 CMPS 3130/6130 Computational Geometry

5. Rotation Left: 4 Right: 3 Rotate around this point now 3/31/20 5 CMPS 3130/6130 Computational Geometry

6. Rotation Left: 4 Right: 4 3/31/20 6 CMPS 3130/6130 Computational Geometry

7. Rotation Left: 3 Right: 4 rotate 3/31/20 7 CMPS 3130/6130 Computational Geometry

8. Rotation Left: 3 Right: 4 rotate 3/31/20 8 CMPS 3130/6130 Computational Geometry

9. Rotation Left: 4 Right: 3 rotate 3/31/20 9 CMPS 3130/6130 Computational Geometry

10. Rotation Left: 3 Right: 4 rotate 3/31/20 10 CMPS 3130/6130 Computational Geometry

11. Rotation Left: 4 Right: 3 rotate 3/31/20 11 CMPS 3130/6130 Computational Geometry

12. Rotation Left: 2 Right: 4 Rotate around this point now 3/31/20 12 CMPS 3130/6130 Computational Geometry

13. Rotation Left: 4 Right: 4 Rotate around this point now 3/31/20 13 CMPS 3130/6130 Computational Geometry

14. Rotation Left: 4 Right: 3 rotate 3/31/20 14 CMPS 3130/6130 Computational Geometry

15. Rotation Left: 3 Right: 4 rotate 3/31/20 15 CMPS 3130/6130 Computational Geometry

16. Rotation Left: 4 Right: 3 rotate 3/31/20 16 CMPS 3130/6130 Computational Geometry

17. Rotation Left: 4 Right: 4 3/31/20 17 CMPS 3130/6130 Computational Geometry

18. Proof Continued In general, choose the rotation point such that the number of points on each side of l does not change. k points m points rotate rotate m points k points 3/31/20 18 CMPS 3130/6130 Computational Geometry

19. Proof Continued Throughout the rotation, there are at most |P|/2 points on each side of l. After 180 rotation, we get the line which is l but directed in the other direction. Let t be the number of blue points to the left of l in the beginning. In the end, t points are on the right side of l, so |Q|-t-1 are on the left side. Therefore, there must have been one orientation of l such that there were at most |Q|/2 points on each side of l. 3/31/20 19 CMPS 3130/6130 Computational Geometry