The document (see pic. below) states that it is possible to find a cover of the plane by a subset of 3 half-planes. It proposes to use linear programming for this. How to formulate such a program?

enter image description here

The original document can be found here: On the Separation of a Polyhedron from Its Single-Part Mold.

EDIT: For clarity: i need to understand how can i use LP to find subcoverage of size 3 from coverage of bigger size.

  • $\begingroup$ Have you looked at reference [10]? $\endgroup$ – Yuval Filmus Jul 2 '18 at 8:59
  • $\begingroup$ What document is your image taken from? You should give credit to the authors, and provide a link to the original. $\endgroup$ – Yuval Filmus Jul 2 '18 at 8:59
  • $\begingroup$ @YuvalFilmus looks like it is paywalled. $\endgroup$ – Yola Jul 2 '18 at 9:11
  • $\begingroup$ Sometimes there are free versions available on authors' websites. $\endgroup$ – Yuval Filmus Jul 2 '18 at 9:13
  • 1
    $\begingroup$ Can you explain what you already know, and what you are looking for? $\endgroup$ – Yuval Filmus Jul 2 '18 at 10:13

I believe the connection between Helly's theorem and linear programming stems from this paper:

Amenta, Nina. "Helly-type theorems and generalized linear programming." Discrete & Computational Geometry 12, no. 3 (1994): 241-261. (Springer link.)

This arose from Nina Amenta's Ph.D. thesis (PDF download), under the direction of Raimund Seidel.

  • $\begingroup$ thanks! very promising, hopefully i will have time to digest it. if i will find solution there i will accept your answer. $\endgroup$ – Yola Jul 2 '18 at 11:31

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.