Оптимизация площади простых многоугольников

Рассматриваются задачи оптимизации площади простого многоугольника для заданного множества вершин P и показывается, что эти задачи тесно связаны с задачами оптимизации числа точек из множества Q, содержащихся в простом многоугольнике с множеством вершин P. Доказывается, что поиск многоугольника минимального или максимального веса для заданного множества вершин является NP-полной задачей, что приводит к доказательству NP-полноты соответствующих задач оптимизации площади. Показывается, что можно найти многоугольник, площадь которого превышает половину площади AR(conv(P)) выпуклой оболочки conv(P) множества P; кроме того, доказывается, что определение существования простого многоугольника площадью не менее (3/2 + ε)AR(conv(P)) является NP-полной задачей. Наконец, доказывается, что при 1 ≤ k ≤ d и 2 ≤ d минимизация объёма k-мерных граней d-мерного простого невырожденного многогранника с заданным множеством вершин является NP-трудной задачей, что отвечает на обобщённый вариант вопроса, сформулированного О’Рурком в 1980 году.