В вычислительной геометрии , A - схема питания , которая также называется диаграмма лагерр-Вороной , ячейки Дирихля сложной , радикал Вороной тесселяции или сечения тесселяции Дирихля , является разбиением евклидовой плоскости в многоугольные клетки , определенных из набора окружностей. Ячейка для данного круга C состоит из всех точек, для которых расстояние до C меньше, чем расстояние до других кругов. Диаграмма мощности представляет собой форму обобщенной диаграммы Вороного, и совпадает с диаграммой Вороного центров окружностей в случае, если все окружности имеют одинаковые радиусы. [1] [2] [3] [4]
Определение
Если С представляет собой окружность , и Р является точкой вне C , то мощность из P относительно C представляет собой квадрат длины отрезки от Р до точки Т касания с С . Эквивалентно, если P находится на расстоянии d от центра круга, а круг имеет радиус r , то (по теореме Пифагора ) степень равна d 2 - r 2 . Та же самая формула d 2 - r 2 может быть распространена на все точки на плоскости, независимо от того, находятся ли они внутри или за пределами C : точки на C имеют нулевую мощность, а точки внутри C имеют отрицательную мощность. [2] [3] [4]
Диаграмма мощности множества п окружностей С я разбиение плоскости на п области R я ( так называемые клетки), таким образом, что точка P принадлежит R я всякий раз , когда окружность С я есть окружность минимизации мощности P . [2] [3] [4]
В случае n = 2 диаграмма мощности состоит из двух полуплоскостей , разделенных линией, называемой радикальной осью или хордалью двух окружностей. Вдоль радикальной оси обе окружности имеют одинаковую мощность. В более общем смысле, в любой диаграмме мощности каждая ячейка R i является выпуклым многоугольником , пересечением полупространств, ограниченных радикальными осями окружности C i, друг с другом окружностью. Тройки клеток встречаются в вершинах диаграммы, которые являются радикальными центрами трех окружностей, клетки которых пересекаются в вершине. [2] [3] [4]
Связанные конструкции
Диаграмму мощности можно рассматривать как взвешенную форму диаграммы Вороного для набора точечных узлов, разбиение плоскости на ячейки, внутри которых одна из площадок находится ближе, чем все остальные. Другие формы взвешенной диаграммы Вороного включают аддитивно взвешенную диаграмму Вороного, в которой каждый сайт имеет вес, который добавляется к его расстоянию перед его сравнением с расстояниями до других сайтов, и мультипликативно взвешенную диаграмму Вороного, в которой вес сайт умножается на его расстояние, прежде чем сравнивать его с расстояниями до других сайтов. Напротив, на диаграмме мощности мы можем рассматривать центр каждого круга как участок, а квадрат радиуса каждого круга как вес, который вычитается из квадрата евклидова расстояния перед его сравнением с другими квадратами расстояний. В случае, если все радиусы окружностей равны, это вычитание не влияет на сравнение, а диаграмма мощности совпадает с диаграммой Вороного. [3] [4]
Планарную диаграмму мощности также можно интерпретировать как плоское поперечное сечение невзвешенной трехмерной диаграммы Вороного. В этой интерпретации множество центров окружностей в плоскости поперечного сечения являются перпендикулярными проекциями трехмерных узлов Вороного, а квадрат радиуса каждого круга является константой K минус квадрат расстояния от соответствующего участка до перекрестия. плоскость сечения, где K выбирается достаточно большим, чтобы все радиусы были положительными. [5]
Как и диаграмма Вороного, диаграмма мощности может быть обобщена на евклидовы пространства любой размерности. Диаграмма мощности n сфер в d измерениях комбинаторно эквивалентна пересечению набора n обращенных вверх полупространств в d + 1 измерениях, и наоборот. [3]
Алгоритмы и приложения
Двумерные диаграммы мощности могут быть построены с помощью алгоритма, который выполняется за время O ( n log n ). [2] [3] В более общем смысле, из-за эквивалентности с пересечениями полупространств более высокой размерности, d -мерные диаграммы мощности (для d > 2) могут быть построены с помощью алгоритма, работающего во времени. [3]
Диаграмма мощности может использоваться как часть эффективного алгоритма для вычисления объема объединения сфер. Пересечение каждой сферы с ее ячейкой диаграммы мощности дает ее вклад в общее объединение, из которого можно вычислить объем во времени, пропорциональном сложности диаграммы мощности. [6]
Другие применения диаграмм мощности включают структуры данных для проверки принадлежности точки к объединению дисков, [2] алгоритмы построения границы объединения дисков [2] и алгоритмы нахождения ближайших двух шаров в наборе шаров. . [7]
История
Ауренхаммер (1987) прослеживает определение степенного расстояния до работ математиков XIX века Эдмона Лагерра и Георгия Вороного . [3] Фейес Тот (1977) определил диаграммы мощности и использовал их, чтобы показать, что граница объединения n круглых дисков всегда может быть освещена не более чем 2 n точечными источниками света. [8] Диаграммы мощности появлялись в литературе под другими названиями, включая «диаграмму Лагерра – Вороного», «клеточный комплекс Дирихле», «радикальную тесселяцию Вороного» и «секционную тесселяцию Дирихле». [9]
Рекомендации
- ^ Лингарт, J. (1981), "Dirichletsche Zellenkomplexe мит maximaler Eckenzahl", Geometriae Dedicata , 11 (3): 363-367, DOI : 10.1007 / BF00149360 , МР 0627538.
- ^ Б с д е е г Имаи, Хироши; Ири, Масао; Murota, Кадзуо (1985), "диаграмма Вороного в геометрии Лагерра и его применения", SIAM журнал по вычислениям , 14 (1): 93-105, DOI : 10,1137 / 0214006 , МР 0774929.
- ^ Б с д е е г ч I Aurenhammer, Ф. (1987), "Электрические схемы: свойства, алгоритмы и приложения", SIAM журнал по вычислениям , 16 (1): 78-96, DOI : 10,1137 / 0216006 , МР 0873251.
- ^ а б в г д Эдельсбруннер, Герберт (1987), «Диаграммы мощности 13.6», Алгоритмы в комбинаторной геометрии , Монографии EATCS по теоретической информатике, 10 , Springer-Verlag, стр. 327–328.
- ^ Эш, Питер Ф .; Bolker, Этан Д. (1986), "Обобщенные мозаики Дирихля", Geometriae Dedicata , 20 (2): 209-243, DOI : 10.1007 / BF00164401 , МР 0833848.
- ^ Авис, Дэвид ; Bhattacharya, Binay K .; Имаи, Hiroshi (1988), "Вычисление объема объединения сфер" (PDF) , Визуальный Компьютер , 3 (6): 323-328, DOI : 10.1007 / BF01901190.
- ^ Гибас, Леонид ; Чжан Ли (1998), "Евклидовы диаграммы близости и мощности", 10-я Канадская конференция по вычислительной геометрии.
- ^ Фейес Тота, Л. (1977), "Освещение выпуклых дисков", Acta Mathematica Academiae Scientiarum Hungaricae , 29 (3-4): 355-360, DOI : 10.1007 / BF01895856 , МР 0464065.
- ^ Aurenhammer, F .; Имаи, Х. (1988), "Геометрические соотношения между диаграмм Вороного", Geometriae Dedicata , 27 (1): 65-75, DOI : 10.1007 / BF00181613 , МР 0950323.