Эффективные алгоритмы вычисления модальности многоугольников

Рассматривается задача вычисления модальности многоугольников. Для выпуклого многоугольника с $n$ вершинами получен $O(n\log n)$ алгоритм. Доказано, что алгоритм оптимален. Для вычисления модальностей вершин выпуклого многоугольника представлен алгоритм с такой же временной оценкой. Для простого многоугольника построен $O(n^\alpha\log n)$ алгоритм вычисления модальности, где $\alpha=2-1/\log(\sqrt5+1)\approx1.41$. Для вычисления модальностей вершин простого многоугольника получен $O(n^\beta)$ алгоритм, где $\beta=\log(\sqrt5+1)\approx1.695$. Алгоритмы улучшают временные оценки, полученные Агарвалом – Мелвиллом (1986).