Аксиальность (геометрия) - Axiality (geometry)

В геометрии Евклидова плоскость, ось это мера того, сколько осевая симметрия форма имеет. Он определяется как отношение площадей наибольшего аксиально-симметричного подмножества формы ко всей форме. Эквивалентно, это самая большая часть площади формы, которая может быть покрыта зеркальным отражением формы (с любой ориентацией).

Форма, которая сама по себе является осесимметричной, например равнобедренный треугольник, будет иметь ось ровно один, тогда как асимметричная форма, такая как неравносторонний треугольник, будет иметь ось меньше единицы.

Верхняя и нижняя границы

Лассак (2002) показал, что каждый выпуклый набор имеет ось не менее 2/3.^[1] Этот результат улучшил предыдущую нижнюю границу 5/8 на Краковский (1963).^[2] Наилучшая известная верхняя оценка дается конкретным выпуклым четырехугольник, найденные с помощью компьютерного поиска, ось которого меньше 0,816.^[3]

За треугольники и для центрально-симметричный Для выпуклых тел ось всегда несколько выше: каждый треугольник и каждое центрально-симметричное выпуклое тело имеет ось не менее ${\displaystyle 2({\sqrt {2}}-1)\approx 0.828}$. В множестве тупых треугольников, вершины которых имеют ${\displaystyle x}$-координаты ${\displaystyle 0}$, ${\displaystyle {\sqrt {2}}}$, и ${\displaystyle 1}$, ось приближается ${\displaystyle 2({\sqrt {2}}-1)}$ в пределе как ${\displaystyle y}$-координаты приближаются к нулю, показывая, что нижняя граница максимально велика. Также возможно построить последовательность центрально-симметричных параллелограммы ось которого имеет тот же предел, что снова показывает, что нижняя граница жесткая.^[4][5]

Алгоритмы

Оси данной выпуклой формы можно сколь угодно точно аппроксимировать в сублинейном времени, учитывая доступ к форме оракулам для нахождения крайней точки в данном направлении и для нахождения пересечения формы с линией.^[6]

Барекет и Роголь (2007) рассмотрим задачу точного вычисления аксиальности как для выпуклых, так и для невыпуклых многоугольников. Множество всех возможных линий симметрии отражения на плоскости есть (по проективная двойственность ) двумерное пространство, которое они разделяют на ячейки, внутри которых фиксируется схема пересечения многоугольника с его отражением, в результате чего ось плавно изменяется внутри каждой ячейки. Таким образом, они сводят проблему к числовому вычислению в каждой ячейке, которое они не решают явно. Разбиение плоскости на ячейки имеет ${\displaystyle O(n^{4})}$ ячеек в общем случае и ${\displaystyle O(n^{3})}$ ячейки для выпуклых многоугольников; его можно построить за время, превышающее эти границы на логарифмический коэффициент. Барекет и Роголь утверждают, что на практике задача максимизации площади в пределах одной ячейки может быть решена за ${\displaystyle O(n)}$ время, давая (нестрогие) общие временные рамки ${\displaystyle O(n^{4})}$ для выпуклого случая и ${\displaystyle O(n^{5})}$ для общего случая.^[7]

Связанные понятия

де Валькур (1966) перечисляет 11 различных мер осевой симметрии, из которых описанная здесь третья.^[8] Он требует, чтобы каждая такая мера была инвариантной относительно преобразования подобия данной формы, чтобы принять значение один для симметричных фигур и принять значение от нуля до единицы для других фигур. Другие меры симметрии с этими свойствами включают отношение площади формы к ее наименьшему охватывающему симметричному надмножеству и аналогичные отношения периметров.

Лассак (2002) Помимо изучения осевой направленности, изучает ограниченную версию осевой ориентации, в которой цель состоит в том, чтобы найти полупространство, пересечение которого с выпуклой формой имеет большую площадь, полностью лежащую в пределах отражения формы через границу полупространства. Он показывает, что такое пересечение всегда может иметь площадь не менее 1/8 площади всей формы.^[1]

При изучении компьютерное зрение, Марола (1989) предложил измерить симметрию цифровое изображение (рассматривается как функция ${\displaystyle w}$ от точек на плоскости к оттенки серого значения интенсивности в интервале ${\displaystyle 0\leq w(p)\leq 1}$) найдя отражение ${\displaystyle \sigma }$ который максимизирует интеграл площадей^[9]

${\displaystyle {\frac {\int \int w(p)w(\sigma (p))dx\,dy}{\int \int w(p)^{2}dx\,dy}}.}$

Когда ${\displaystyle w}$ это индикаторная функция заданной формы, это то же самое, что и ось.

Рекомендации

1. Лассак, Марек (2002), "Аппроксимация выпуклых тел аксиально-симметричными телами", Труды Американского математического общества, 130 (10): 3075–3084 (электронная), Дои:10.1090 / S0002-9939-02-06404-3, МИСТЕР  1908932. Erratum, Дои:10.1090 / S0002-9939-03-07225-3.
2. Краковский, Ф. (1963), "Bemerkung zu einer Arbeit von W. Nohl", Elemente der Mathematik, 18: 60–61. Как цитирует де Валькур (1966).
3. Чой, Чанг-Юль (2006), Нахождение наибольшего вписанного аксиально-симметричного многоугольника для выпуклого многоугольника (PDF), Кандидатская диссертация, факультет электротехники и информатики Корейского передового института науки и технологий.
4. Ноль, В. (1962), "Die innere axiale Symmetrie zentrischer Eibereiche der euklidischen Ebene", Elemente der Mathematik, 17: 59–63. Как цитирует де Валькур (1966).
5. Буда, Анджей Б .; Мислоу, Курт (1991), «О мере аксиальности треугольных областей», Elemente der Mathematik, 46 (3): 65–73, МИСТЕР  1113766.
6. Ан, Хи-Кап; Брасс, Питер; Чеонг, Отфрид; На, Хён Сок; Шин, Чан-Су; Виньерон, Антуан (2006), «Вписывание аксиально-симметричного многоугольника и другие алгоритмы аппроксимации для плоских выпуклых множеств», Вычислительная геометрия, 33 (3): 152–164, Дои:10.1016 / j.comgeo.2005.06.001, HDL:10203/314, МИСТЕР  2188943.
7. Барекет, Гилл; Роголь, Вадим (2007), «Максимизация площади аксиально-симметричного многоугольника, вписанного в простой многоугольник» (PDF), Компьютеры и графика, 31 (1): 127–136, Дои:10.1016 / j.cag.2006.10.006.
8. де Валькур, Б. Абель (1966), "Меры осевой симметрии для овалов", Израильский математический журнал, 4: 65–82, Дои:10.1007 / BF02937452, МИСТЕР  0203589.
9. Марола, Джованни (1989), "Об обнаружении осей симметрии симметричных и почти симметричных плоских изображений", IEEE Transactions по анализу шаблонов и машинному анализу, 11 (1): 104–108, Дои:10.1109/34.23119