Suchen Sie eine gerade Linie, um zwei konvexe Polygone durch die gleiche Fläche zu teilen

Nehmen wir an , wir haben zwei nicht überlappenden konvexen Polygonen und . Wie können wir eine gerade Linie zeichnen, die in zwei Teile gleicher Fläche und auch in zwei Teile gleicher Fläche teilt ? Können wir dies auch in der Komplexität oder besser tun ? ( )$A$$B$$A$$B$$O(n^2)$$n = |A| + |B|$

Dies ist als Ham-Sandwich-Theorem bekannt :

Bei zwei messbaren Objekten im zweidimensionalen euklidischen Raum ist es möglich, jedes von ihnen mit einer Linie in Hälften zu teilen.$2$

Hinweis: Konvexität ist nicht erforderlich. Und$\mathbb{R}^2$ kann ersetzt werden durch $\mathbb{R}^d$ mit "Linie" ersetzt durch a $(d{-}1)$-dimensionale Hyperebene.

Als Antwort auf die Anfrage von @ WillardZhan hinzugefügt:

Ivan Stojmenovíc. Halbierungen und Schinkensandwichschnitte von konvexen Polygonen und Polyedern. Inf. Prozess. Lette. 38 (1): 15-21. 1991. ( CiteSeer PDF-Download .)
Zusammenfassung . Wir präsentieren einen linearen zeitsequenziellen Algorithmus zum Finden einer geraden Linie, die zwei gegebene disjunkte konvexe Polygone halbiert (dh beide in Teile gleicher Fläche schneidet).

Abbott, Timothy G., Erik D. Demaine, Martin L. Demaine, Daniel M. Kane, Stefan Langerman, Jelani Nelson und Vincent Yeung. "Dynamische Schinkensandwichschnitte konvexer Polygone in der Ebene." In CCCG , S. 61-64. 2005. ( PDF-Download .)