Осевое положение (геометрия)

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

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

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

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

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

Алгоритмы

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

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

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

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

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

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

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

Когда $w$ – индикаторная функция данной формы, это то же самое, что и аксиальность.

Ссылки

^ Jump up to: ^а ^б Лассак, Марек (2002), «Приближение выпуклых тел осесимметричными телами», Труды Американского математического общества , 130 (10): 3075–3084 (электронный), doi : 10.1090/S0002-9939-02-06404-3 , МР 1908932 . Опечатка, два : 10.1090/S0002-9939-03-07225-3 .
^ Краковски, Ф. (1963), «Примечание к статье В. Нола», Elements of Mathematics , 18 : 60–61 . Цитируется де Валькуром (1966) .
^ Чхве, Чанг-Юл (2006), «Нахождение наибольшего вписанного осесимметричного многоугольника для выпуклого многоугольника» (PDF) , магистерская диссертация, факультет электротехники и информатики, Корейский институт передовых наук и технологий .
^ Нол, В. (1962), «Внутренняя осевая симметрия центрических яичных областей евклидовой плоскости», Elements of Mathematics , 17 : 59–63 . Цитируется де Валькуром (1966) .
^ Буда, Анджей Б.; Мислоу, Курт (1991), «О мере аксиальности треугольных областей» , Elemente der Mathematik , 46 (3): 65–73, MR 1113766 .
^ Ан, Хи-Кап; Брасс, Питер; Чеонг, Отфрид; На, Хён Сок; Шин, Чан-Су; Виньерон, Антуан (2006), «Вписание осесимметричного многоугольника и другие алгоритмы аппроксимации плоских выпуклых множеств», Computational Geometry , 33 (3): 152–164, doi : 10.1016/j.comgeo.2005.06.001 , hdl : 10203 /314 , МР 2188943 .
^ Бареке, Гилл; Роголь, Вадим (2007), «Максимизация площади осесимметричного многоугольника, вписанного в простой многоугольник» (PDF) , Computers & Graphics , 31 (1): 127–136, doi : 10.1016/j.cag.2006.10.006 .
^ де Валькур, Б. Абель (1966), «Меры осевой симметрии овалов», Израильский математический журнал , 4 (2): 65–82, doi : 10.1007/BF02937452 , MR 0203589 .
^ Марола, Джованни (1989), «Об обнаружении осей симметрии симметричных и почти симметричных плоских изображений», IEEE Transactions on Pattern Analysis and Machine Intelligence , 11 (1): 104–108, doi : 10.1109/34.23119

[lassak02-1] Jump up to: ^а ^б Лассак, Марек (2002), «Приближение выпуклых тел осесимметричными телами», Труды Американского математического общества , 130 (10): 3075–3084 (электронный), doi : 10.1090/S0002-9939-02-06404-3 , МР 1908932 . Опечатка, два : 10.1090/S0002-9939-03-07225-3 .

[2] Краковски, Ф. (1963), «Примечание к статье В. Нола», Elements of Mathematics , 18 : 60–61 . Цитируется де Валькуром (1966) .

[3] Чхве, Чанг-Юл (2006), «Нахождение наибольшего вписанного осесимметричного многоугольника для выпуклого многоугольника» (PDF) , магистерская диссертация, факультет электротехники и информатики, Корейский институт передовых наук и технологий .

[4] Нол, В. (1962), «Внутренняя осевая симметрия центрических яичных областей евклидовой плоскости», Elements of Mathematics , 17 : 59–63 . Цитируется де Валькуром (1966) .

[5] Буда, Анджей Б.; Мислоу, Курт (1991), «О мере аксиальности треугольных областей» , Elemente der Mathematik , 46 (3): 65–73, MR 1113766 .

[6] Ан, Хи-Кап; Брасс, Питер; Чеонг, Отфрид; На, Хён Сок; Шин, Чан-Су; Виньерон, Антуан (2006), «Вписание осесимметричного многоугольника и другие алгоритмы аппроксимации плоских выпуклых множеств», Computational Geometry , 33 (3): 152–164, doi : 10.1016/j.comgeo.2005.06.001 , hdl : 10203 /314 , МР 2188943 .

[7] Бареке, Гилл; Роголь, Вадим (2007), «Максимизация площади осесимметричного многоугольника, вписанного в простой многоугольник» (PDF) , Computers & Graphics , 31 (1): 127–136, doi : 10.1016/j.cag.2006.10.006 .

[8] де Валькур, Б. Абель (1966), «Меры осевой симметрии овалов», Израильский математический журнал , 4 (2): 65–82, doi : 10.1007/BF02937452 , MR 0203589 .

[9] Марола, Джованни (1989), «Об обнаружении осей симметрии симметричных и почти симметричных плоских изображений», IEEE Transactions on Pattern Analysis and Machine Intelligence , 11 (1): 104–108, doi : 10.1109/34.23119

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]