Найти C-выпуклые отверстия в плоской точки

Question

Я ищу эффективный алгоритм, чтобы найти выпуклые отверстия в заданном задании. Проблема в

Учитывая $ n $ Точки на плоскости евклидана и константы $ C $ , определить, как Многие пустые выпуклые многоугольники $ p_1, \ dots, p_k $ Есть, так что для каждого $ i= 1, \ dots , K $ ; $ p_i $ имеет ровно $ C $ вершины из заданного набора точек.

Хотя есть некоторые документы, которые считают поиск, возможно, не выпуклые отверстия [1] [2] [3] и некоторые другие, которые показывают наличие таких отверстий [4] [5] , я не мог найти бумагу, которая описывает алгоритм, чтобы найти их.

Очевидно, что наивный алгоритм, который работает в $ \ mathcal {o} (n ^ c) $ , где каждый $ c $ l -ssset проходит. Однако я хотел бы узнать, существует ли более эффективный алгоритм.

Answer 1

в "Подсчет выпуклых многоугольников в плоских наборах точек" ( ссылка ) mitchell et al.Показать алгоритм, который может сделать это во времени $ o (Cn ^ 3) $ .

Однако, однако, что если вам нужно сообщать о тех полигонах, то вы не можете сделать лучше, чем $ O (N ^ C) $ , как может быть <класс SPAR= «Математический контейнер»> $ \ Omega (n ^ c) $ Такие многоугольники для начала (рассмотрим, например, $ n $ Точки в выпуклой позиции).