Толстый объект (геометрия)

В геометрии — толстый объект это объект в двух или более измерениях, длина которого в разных измерениях одинакова. Например, квадрат толстый, потому что его длина и ширина одинаковы. 2 на 1 Прямоугольник тоньше квадрата, но он толще прямоугольника 10 на 1. Точно так же круг толще, чем эллипс 1 на 10 , а равносторонний треугольник толще, чем очень тупой треугольник .

Толстые объекты особенно важны в вычислительной геометрии . Многие алгоритмы вычислительной геометрии могут работать намного лучше, если их входные данные состоят только из толстых объектов; см. раздел приложений ниже.

Глобальная упитанность

Учитывая константу R ≥1, объект o называется R -толстым , если его «коэффициент стройности» не превышает R . «Фактор стройности» в разных работах имеет разное определение. Общее определение ^[1] является:

{\frac {{\text{side of smallest cube enclosing}}\ o}{{\text{side of largest cube enclosed in}}\ o}}

где o и кубы - мерны d . Двумерный куб — это квадрат , поэтому коэффициент тонкости квадрата равен 1 (поскольку его наименьший охватывающий квадрат такой же, как и его самый большой замкнутый диск). Коэффициент стройности прямоугольника 10х1 равен 10. Коэффициент стройности круга равен √2. Следовательно, согласно этому определению, квадрат имеет 1 толщину, но диск и прямоугольник 10 × 1 не являются 1-жирными. Квадрат тоже 2-жирный (поскольку его коэффициент тонкости меньше 2), 3-жирный и т. д. Диск тоже 2-жирный (а также 3-жирный и т. д.), но прямоугольник 10×1 не является 2-жирным. -толстый. Любая фигура является ∞-толстой, поскольку по определению коэффициент тонкости всегда не превосходит ∞.

Приведенное выше определение можно назвать жирностью двух кубов, поскольку оно основано на соотношении длин сторон двух кубов. Аналогичным образом можно определить упитанность двух шаров , в которых d-мерный шар . вместо этого используется ^[2] Двумерный шар — это диск . Согласно этому альтернативному определению, диск имеет 1 толщину, но квадрат не имеет 1 толщины, поскольку его тонкость с двумя шарами равна √2.

Альтернативное определение, которое можно назвать упитанностью окружающего шара (также называемой «толщиной»). ^[3]) основан на следующем коэффициенте тонкости:

\left({\frac {{\text{volume of smallest ball enclosing}}\ o}{{\text{volume of}}\ o}}\right)^{1/d}

Показатель степени 1/ d делает это определение отношением двух длин, так что его можно сравнить с жирностью двух шаров.

Здесь тоже вместо мяча можно использовать кубик.

Аналогичным образом можно определить упитанность закрытого шара на основе следующего коэффициента стройности:

\left({\frac {{\text{volume of}}\ o}{{\text{volume of largest  ball enclosed in}}\ o}}\right)^{1/d}

Окружающая жирность против закрытой жирности

Тонкость окружающего шара/куба может сильно отличаться от тонкости закрытого шара/куба.

Например, рассмотрим леденец с конфетой в форме квадрата 1×1 и палочку в форме прямоугольника b ×(1/ b ) (при b >1>(1/ b )). С увеличением b площадь объемлющего куба (≈ b ²) увеличивается, но площадь закрытого куба остается постоянной (=1), а общая площадь фигуры также остается постоянной (=2). Таким образом, тонкость охватывающего куба может увеличиваться произвольно, в то время как тонкость замкнутого куба остается постоянной (=√2). См. эту страницу GeoGebra для демонстрации.

С другой стороны, рассмотрим прямолинейную «змею» шириной 1/b и длиной b , которая полностью сложена внутри квадрата с длиной стороны 1. По мере увеличения b площадь замкнутого куба (≈1/ b ²) уменьшается, но общие площади змеи и окружающего куба остаются постоянными (=1). Таким образом, тонкость замкнутого куба может увеличиваться произвольно, в то время как тонкость охватывающего куба остается постоянной (=1).

И у леденца, и у змейки двухкубик-стройность растет произвольно, так как в общем случае:

тонкость закрытого шара ⋅ тонкость закрытого шара = тонкость двух шаров

Тонкость окружающего куба ⋅ Тонкость закрытого куба = Тонкость двух кубов

Поскольку все коэффициенты тонкости не менее 1, из этого следует, что если объект o является R-толстым в соответствии с определением двух шаров/кубов, он также является R-толстым в соответствии с охватывающим шаром/кубом и закрытым шаром/кубом. определения (но обратное неверно, как показано выше).

Шарики против кубиков

Объем d - мерного шара радиуса r равен : $V_{d}\cdot r^{d}$ , где V _d — константа, зависящая от размерности:

V_{d}={\frac {\pi ^{d/2}}{\Gamma ({\frac {d}{2}}+1)}}

D -мерный куб со стороной 2 a имеет объем (2 a ) ^д. Он заключен в d -мерный шар радиуса a√d, объем которого равен V _d ( a√d ) ^д. Следовательно, для каждого d -мерного объекта:

тонкость окружающего шара ≤ тонкость окружающего куба ⋅

{V_{d}}^{1/d}\cdot {\sqrt {d}}/2

.

Для четных размеров ( d =2 k ) коэффициент упрощается до: ${\sqrt {0.5\pi k}}/{{(k!)}^{1/2k}}$ . В частности, для двумерных форм V ₂ =π и коэффициент равен: √(0,5 π)≈1,25, поэтому:

тонкость окружающего диска ≤ тонкость окружающего квадрата ⋅ 1,25

Из аналогичных соображений:

тонкость закрытого куба ≤ тонкость закрытого шара ⋅

{V_{d}}^{1/d}\cdot {\sqrt {d}}/2

тонкость закрытого квадрата ≤ тонкость закрытого диска ⋅ 1,25

D -мерный шар радиуса a заключен в d -мерный куб с длиной стороны 2 a . Следовательно, для каждого d -мерного объекта:

тонкость-куба ≤ тонкость-шара ⋅

2/{V_{d}}^{1/d}

Для четных размеров ( d =2 k ) коэффициент упрощается до: $2/{(k!)}^{1/2k}/{\sqrt {\pi }}$ . В частности, для двумерных фигур коэффициент равен: 2/√π≈1,13, поэтому:

тонкость квадрата корпуса ≤ тонкость корпуса ⋅ 1,13

Из аналогичных соображений:

тонкость закрытого шара ≤ тонкость закрытого куба ⋅

2/{V_{d}}^{1/d}

Тонкость закрытого диска ≤ тонкость закрытого квадрата ⋅ 1,13

Умножение приведенных выше отношений дает следующие простые отношения:

тонкость двух шаров ≤ тонкость двух кубов ⋅ √ d

тонкость двух кубов ≤ тонкость двух шаров ⋅ √ d

Таким образом, объект R -fat согласно определению двух шаров или двух кубов является не более чем R √ d -fat согласно альтернативному определению.

Местная упитанность

Все приведенные выше определения являются глобальными в том смысле, что они не учитывают небольшие тонкие области, являющиеся частью большого толстого объекта.

Например, рассмотрим леденец с конфетой в форме квадрата 1×1 и палочку в форме прямоугольника 1×(1/ b ) (при b >1>(1/ b )). По мере увеличения b площадь окружающего куба (=4) и площадь окружающего куба (=1) остаются постоянными, в то время как общая площадь фигуры меняется лишь незначительно (=1+1/ b ). Таким образом, все три фактора тонкости ограничены: тонкость объемлющего куба≤2, тонкость закрытого куба≤2, тонкость двухкубов=2. Таким образом, по всем определениям леденец 2-жирный. Однако палочка леденца явно становится тоньше и тоньше.

В некоторых приложениях такие тонкие детали неприемлемы, поэтому более подходящей может быть локальная упитанность , основанная на локальном коэффициенте тонкости. Для каждого глобального фактора тонкости можно определить локальную версию. Например, для тонкости охватывающего шара можно определить коэффициент локальной тонкости охватывающего шара объекта o, рассматривая множество B всех шаров, центр которых находится внутри o и граница которых пересекает границу o ( т.е. не полностью содержащий o ). Коэффициент локальной тонкости охватывающего шара определяется как: ^[3]^[4]

{\frac {1}{2}}\cdot \sup _{b\in B}\left({\frac {{\text{volume of}}\ B}{{\text{volume of}}\ B\cap o}}\right)^{1/d}

1/2 — это коэффициент нормализации, который делает локальную тонкость окружающего шара шара равной 1. В локальной тонкости окружающего шара формы леденца, описанной выше, доминирует 1×(1/ b ) прилипает и переходит в ∞ по мере роста b . Таким образом, по местному определению вышеуказанный леденец не является 2-жирным.

Глобальные и локальные определения

Локальная жирность подразумевает глобальную жирность. Вот примерный эскиз упитанности на основе вмещающих шариков. По определению, объем наименьшего объемлющего шара равен объему любого другого объемлющего шара. В частности, это ≤ объем любого объемлющего шара, центр которого находится внутри o и граница которого касается границы o . Но каждый такой объемлющий шар входит в множество B, рассматриваемое по определению тонкости локального охватывающего шара. Следовательно:

тонкость корпуса шара ^д =

= объем (наименьший охватывающий шар)/объем ( o )

≤ объем(охватывающий шар- b -в- B )/объем( o )

= объем (охватывающий шар- b -в- B )/объем ( b ∩ o )

≤ (2 локальная тонкость охватывающего шара) ^д

Следовательно:

тонкость охватывающего шара ≤ 2⋅локальная тонкость охватывающего шара

Для выпуклого тела верно и обратное: локальная полнота подразумевает глобальную полноту. Доказательство ^[3] основано на следующей лемме. Пусть o — выпуклый объект. Пусть P — точка в o . Пусть b и B — два шара с центром в точке P, такие что b меньше B . Тогда o пересекает большую часть b , чем B , то есть:

{\frac {{\text{volume}}\ (b\cap o)}{{\text{volume}}\ (b)}}\geq {\frac {{\text{volume}}\ (B\cap o)}{{\text{volume}}\ (B)}}

Схема доказательства: стоя в точке P , мы можем посмотреть под разными углами θ и измерить расстояние до границы o . Поскольку o выпукло, это расстояние является функцией, скажем, r ( θ ). Мы можем вычислить левую часть неравенства, проинтегрировав следующую функцию (умноженную на некоторую детерминантную функцию) по всем углам:

f(\theta )=\min {({\frac {r(\theta )}{{\text{radius}}\ (b)}},1)}

Аналогичным образом мы можем вычислить правую часть неравенства, интегрируя следующую функцию:

F(\theta )=\min {({\frac {r(\theta )}{{\text{radius}}\ (B)}},1)}

Проверив все три возможных случая, можно показать, что всегда $f(\theta )\geq F(\theta )$ . Таким образом, интеграл от f является, по крайней мере, интегралом от F , и отсюда следует лемма.

Определение тонкости локального охватывающего шара учитывает все шары, центрированные в точке o и пересекающие границу o . Однако, когда o выпукло, приведенная выше лемма позволяет нам рассматривать для каждой точки из o только шары максимального размера, т. е. только шары, которые целиком содержат o (и граница которых пересекает границу o ). Для каждого такого шара b :

{\text{volume}}\ (b)\leq C_{d}\cdot {\text{diameter}}\ (o)^{d}

где $C_{d}$ — некоторая константа, зависящая от размерности.

Диаметр o не превышает диаметра наименьшего шара, окружающего o , а объем этого шара равен: $C_{d}\cdot ({\text{diameter(smallest ball enclosing}}\ o)/2)^{d}$ . Объединение всех неравенств дает для каждого выпуклого объекта:

локальная-тонкость-вмещающего-шара ≤ тонкость-вмещающего-шара

Для невыпуклых объектов это неравенство, конечно, не выполняется, как показано на примере леденца выше.

Примеры

В следующей таблице показан коэффициент тонкости различных форм на основе разных определений. Два столбца локальных определений заполняются знаком «*», когда форма выпуклая (в этом случае значение локальной тонкости равно значению соответствующей глобальной тонкости):

Форма	два мяча	два кубика	ограждающий шар	вмещающий куб	закрытый шар	закрытый куб	локальный охватывающий шар	локальный включающий куб
квадрат	√2	1	√(π/2)≈1,25	1	√(4/π) ≈ 1,13	1	*	*
b × прямоугольник с b > a	√(1+b^2/а^2)	б/а	0,5√π(а/б+б/а) ^[3]	√(б/а)	2√(б/аπ)	√(б/а)	*	*
диск	1	√2	1	√(4/π)≈1,13	1	√(π/2)≈1,25	*	*
эллипс с радиусами b > a	б / а	> б / а	√( б / а )	>√( б /2π а )	√( б / а )	>√(π б / а )	*	*
полуэллипс с радиусами b > a , разделенный пополам параллельно b	2 б / а	>2 б / а	√(2 б / а )	>√(4 б /π а )	√(2 б / а )	>√(2π б / а )	*	*
полудиск	2	√5	√2	√(8/π)≈1,6	√2	√(5π/8)≈1,4	*	*
равносторонний треугольник		1+2/√3≈2.15	√(π/√3)≈1,35	√(4/√3)≈1.52		√√3/2+1/√√3≈1.42	*	*
равнобедренный прямоугольный треугольник	1/(√2-1)≈2.4	2		√2		√2	*	*
«леденец» состоит из единичного квадрата и палочки b × a , b >1> a		б +1		√(( б +1)^2/( аб +1))		√( аб +1)		√(б/а)

Жирность треугольника

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

Тонкость закрытого шара

Самая большая окружность, содержащаяся в треугольнике, называется вписанной в него окружностью . Известно , что:

\Delta =r^{2}\cdot (\cot {\frac {\angle A}{2}}+\cot {\frac {\angle B}{2}}+\cot {\frac {\angle C}{2}})

где Δ — площадь треугольника, а r — радиус вписанной окружности. Следовательно, тонкость треугольника по замкнутому шару равна:

{\sqrt {\frac {\cot {\frac {\angle A}{2}}+\cot {\frac {\angle B}{2}}+\cot {\frac {\angle C}{2}}}{\pi }}}

Тонкость корпуса

Наименьшая содержащая окружность для остроугольного треугольника — это описанная окружность , а для тупоугольного треугольника — это круг, диаметр которого равен самой длинной стороне треугольника. ^[5]

Известно , что:

\Delta =R^{2}\cdot 2\sin A\sin B\sin C

где снова Δ — площадь треугольника, а R — радиус описанной окружности. Следовательно, для остроугольного треугольника коэффициент тонкости охватывающего шара равен:

{\sqrt {\frac {\pi }{2\sin A\sin B\sin C}}}

Также известно , что:

\Delta ={\frac {c^{2}}{2(\cot \angle {A}+\cot \angle {B})}}={\frac {c^{2}(\sin \angle {A})(\sin \angle {B})}{2\sin(\angle {A}+\angle {B})}}

где c — любая сторона треугольника, а A , B — прилежащие углы. Следовательно, для тупоугольного треугольника с острыми углами A и B (и самой длинной стороной c ) коэффициент тонкости окружающего шара равен:

{\sqrt {\frac {\pi \cdot (\cot \angle {A}+\cot \angle {B})}{2}}}={\sqrt {\frac {\pi \cdot \sin(\angle {A}+\angle {B})}{2(\sin \angle {A})(\sin \angle {B})}}}

что в прямоугольном треугольнике Обратите внимание , $\sin {\angle {C}}=\sin {\angle {A}+\angle {B}}=1$ , поэтому оба выражения совпадают.

Тонкость двух шаров

Внутренний радиус r и описанный радиус R связаны парой формул, которые дают два альтернативных выражения для тонкости остроугольного треугольника с двумя шарами: ^[6]

{\frac {R}{r}}={\frac {1}{4\sin({\frac {\angle {A}}{2}})\sin({\frac {\angle {B}}{2}})\sin({\frac {\angle {C}}{2}})}}={\frac {1}{\cos \angle {A}+\cos \angle {B}+\cos \angle {C}-1}}

Для тупоугольного треугольника следует использовать c вместо R /2 . По закону синусов :

{\frac {c}{2}}=R\sin {\angle {C}}

Следовательно, коэффициент стройности тупоугольного треугольника с тупым углом C равен:

{\frac {c/2}{r}}={\frac {\sin {\angle {C}}}{4\sin({\frac {\angle {A}}{2}})\sin({\frac {\angle {B}}{2}})\sin({\frac {\angle {C}}{2}})}}={\frac {\sin {\angle {C}}}{\cos \angle {A}+\cos \angle {B}+\cos \angle {C}-1}}

что в прямоугольном треугольнике Обратите внимание , $\sin {\angle {C}}=1$ , поэтому оба выражения совпадают.

Два выражения можно объединить следующим образом, чтобы получить одно выражение для тонкости двух шаров любого треугольника с меньшими углами A и B :

{\frac {\sin {\max(\angle {A},\angle {B},\angle {C},\pi /2)}}{4\sin({\frac {\angle {A}}{2}})\sin({\frac {\angle {B}}{2}})\sin({\frac {\pi -\angle {A}-\angle {B}}{2}})}}={\frac {\sin {\max(\angle {A},\angle {B},\angle {C},\pi /2)}}{\cos \angle {A}+\cos \angle {B}-\cos(\angle {A}+\angle {B})-1}}

Чтобы получить представление о скорости изменения упитанности, рассмотрим, что дает эта формула для равнобедренного треугольника с углом наклона вершины θ , когда θ мал :

{\frac {\sin {\max(\theta ,\pi /2)}}{4\sin ^{2}({\frac {\pi -\theta }{4}})\sin({\frac {\theta }{2}})}}\approx {\frac {1}{4{\sqrt {1/2}}^{2}\theta /2}}={\frac {1}{\theta }}

На следующих графиках показан коэффициент стройности треугольника с двумя шарами:

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

Жирность окружностей, эллипсов и их частей

Тонкость круга на основе шара, конечно же, равна 1 — наименьшему возможному значению.

Для круглого сегмента с центральным углом θ диаметр описанной окружности — это длина хорды, а диаметр вписанной окружности — это высота сегмента, поэтому тонкость двух шаров (и ее приближение, когда θ мало ) равна:

{\frac {\text{length of chord}}{\text{height of segment}}}={\frac {2R\sin {\frac {\theta }{2}}}{R\left(1-\cos {\frac {\theta }{2}}\right)}}={\frac {2\sin {\frac {\theta }{2}}}{\left(1-\cos {\frac {\theta }{2}}\right)}}\approx {\frac {\theta }{\theta ^{2}/8}}={\frac {8}{\theta }}

Для кругового сектора с центральным углом θ (когда θ мало) диаметр описанной окружности — это радиус круга, а диаметр вписанной окружности — это длина хорды, поэтому тонкость двух шаров равна:

{\frac {\text{radius of circle}}{\text{length of chord}}}={\frac {R}{2R\sin {\frac {\theta }{2}}}}={\frac {1}{2\sin {\frac {\theta }{2}}}}\approx {\frac {1}{2\theta /2}}={\frac {1}{\theta }}

Для эллипса коэффициенты тонкости различны в разных местах. Например, рассмотрим эллипс с короткой осью a и длинной осью b . длина аккорда колеблется между $2a\sin {\frac {\theta }{2}}$ на узкой стороне эллипса и $2b\sin {\frac {\theta }{2}}$ на широкой стороне; аналогично высота сегмента колеблется между $b\left(1-\cos {\frac {\theta }{2}}\right)$ на узкой стороне и $a\left(1-\cos {\frac {\theta }{2}}\right)$ на его широкой стороне. Таким образом, тонкость двух шаров варьируется в пределах:

{\frac {2a\sin {\frac {\theta }{2}}}{b\left(1-\cos {\frac {\theta }{2}}\right)}}\approx {\frac {8a}{b\theta }}

и:

{\frac {2b\sin {\frac {\theta }{2}}}{a\left(1-\cos {\frac {\theta }{2}}\right)}}\approx {\frac {8b}{a\theta }}

В общем, когда секущая начинается под углом Θ, коэффициент тонкости можно аппроксимировать следующим образом: ^[7]

{\frac {2\sin {\frac {\theta }{2}}}{\left(1-\cos {\frac {\theta }{2}}\right)}}

\left({\frac {b}{a}}\cos ^{2}(\Theta +{\frac {\theta }{2}})+{\frac {a}{b}}\sin ^{2}(\Theta +{\frac {\theta }{2}})\right)

Жирность выпуклого многоугольника

Выпуклый многоугольник называется r -разделенным , если угол между каждой парой ребер (не обязательно смежных) не менее r .

Лемма: Тонкость объемлющего шара выпуклого многоугольника, разделенного r, не превосходит $O(1/r)$ . ^[8]^: 7–8

Выпуклый многоугольник называется k,r -разделенным , если:

У него нет параллельных ребер, за исключением разве что двух горизонтальных и двух вертикальных.
Каждое ребро, не параллельное оси, составляет угол не менее r с любым другим краем, а также с осями x и y.
Если имеется два горизонтальных ребра, то диаметр/высота не превосходит k .
Если есть два вертикальных ребра, то диаметр/ширина не превышает k .

Лемма: Тонкость объемлющего шара выпуклого многоугольника, разделенного k,r, не превосходит $O(\max(k,1/r))$ . ^[9] улучшить верхнюю границу до $O(d)$ .

Подсчет толстых предметов

Если объект o имеет диаметр 2 a , то каждый шар, охватывающий o, должен иметь радиус не менее a и объем не менее V _d a ^д. Следовательно, по определению жирности объемлющего шара объем R -жирного объекта диаметром 2 a должен быть не менее: V _d a ^д/ Р ^д. Следовательно:

Лемма 1 : Пусть R ≥1 и C≥0 — две константы. Рассмотрим набор непересекающихся d -мерных объектов, которые все глобально R -толстые (т.е. с тонкостью охватывающего шара ≤ R ). Число таких предметов диаметром не менее 2 a , содержащихся в шаре радиуса C⋅a , не превышает:

V_{d}\cdot (Ca)^{d}/(V_{d}\cdot a^{d}/R^{d})=(RC)^{d}

Например (при d =2, R =1 и C =3): Число непересекающихся дисков радиусом не менее 1, содержащихся в круге радиуса 3, не превышает 3. ²=9. (На самом деле их максимум 7).

Если мы рассмотрим локальную жирность вместо глобальной жирности, мы можем получить более сильную лемму: ^[3]

Лемма 2 : Пусть R ≥1 и C≥0 — две константы. Рассмотрим набор непересекающихся d -мерных объектов, которые все являются локально R -толстыми (т.е. с локальной тонкостью охватывающего шара ≤ R ). Пусть o — единственный объект в этой коллекции диаметром 2 a . Тогда количество объектов в коллекции диаметром больше 2 a , находящихся на расстоянии 2C⋅a от объекта o, не превышает:

(4R\cdot (C+1))^{d}

Например (при d =2, R =1 и C =0): количество непересекающихся дисков радиусом больше 1, которые касаются данного единичного диска, не превышает 4. ²=16 (это не точная оценка, поскольку в этом случае легко доказать верхнюю оценку 5).

Обобщения

Следующее обобщение ожирения было изучено ^[2] для двумерных объектов.

Треугольник ∆ — это (β, δ)-треугольник плоского объекта o (0<β≤π/3, 0<δ< 1), если ∆ ⊆ o , то каждый из углов ∆ не меньше β, и длина каждого из его ребер не менее δ·диаметр( o ). Объект o на плоскости называется (β,δ)-покрытым , если для каждой точки P ∈ o существует (β, δ)-треугольник ∆ объекта o , содержащий P.

Для выпуклых объектов эти два определения эквивалентны в том смысле, что если o является α-жирным для некоторой константы α, то оно также (β,δ)-покрыто для соответствующих констант β и δ, и наоборот. Однако для невыпуклых объектов определение «толстости» является более общим, чем определение «(β, δ)-покрытия». ^[2]

Приложения

Жирные объекты используются в различных задачах, например:

Планирование движения . Планирование пути робота, движущегося среди препятствий, становится проще, если препятствиями являются толстые объекты. ^[3]
Честная нарезка торта : разделить торт становится сложнее, если на куски приходится толстые предметы. Это требование является общим, например, когда «пирог», подлежащий разделу, представляет собой земельное поместье. ^[10]
Дополнительные приложения можно найти в ссылках ниже.

Ссылки

^ Кац, MJ (1997). «3D-съемка вертикальными лучами и 2D-точечное наложение, поиск дальности и дуговая стрельба среди выпуклых толстых объектов» (PDF) . Вычислительная геометрия . 8 (6): 299–316. дои : 10.1016/s0925-7721(96)00027-2 . S2CID 122806176 . , Агарвал, ПК; Кац, MJ; Шарир, М. (1995). «Вычисление порядков глубины для толстых объектов и связанные с этим проблемы» . Вычислительная геометрия . 5 (4): 187. дои : 10.1016/0925-7721(95)00005-8 .
^ Перейти обратно: ^а ^б ^с Эфрат, А.; Кац, MJ; Нильсен, Ф.; Шарир, М. (2000). «Динамические структуры данных для толстых объектов и их приложений» . Вычислительная геометрия . 15 (4): 215. дои : 10.1016/s0925-7721(99)00059-0 .
^ Перейти обратно: ^а ^б ^с ^д ^и ^ж Ван дер Стаппен, AF; Гальперин, Д.; Овермарс, Миннесота (1993). «Сложность свободного пространства для робота, движущегося среди толстых препятствий». Вычислительная геометрия . 3 (6): 353. doi : 10.1016/0925-7721(93)90007-s . hdl : 1874/16650 .
^ Берг, М.; Грут, М.; Овермарс, М. (1994). «Новые результаты о разбиениях двоичного пространства на плоскости (расширенный тезис)». Теория алгоритмов — SWAT '94 . Конспекты лекций по информатике. Том. 824. с. 61. дои : 10.1007/3-540-58218-5_6 . ISBN 978-3-540-58218-2 . , Ван дер Стаппен, AF; Овермарс, Миннесота (1994). «Планирование движения среди толстых препятствий (расширенный реферат)». Материалы десятого ежегодного симпозиума по вычислительной геометрии - SCG '94 . п. 31. дои : 10.1145/177424.177453 . ISBN 978-0897916486 . S2CID 152761 . , Овермарс, Миннесота (1992). «Расположение точек в жировых подразделениях». Письма об обработке информации (представленная рукопись). 44 (5): 261–265. дои : 10.1016/0020-0190(92)90211-д . hdl : 1874/17965 . , Овермарс, Миннесота; Ван дер Стаппен, ФА (1996). «Поиск дальности и расположение точек среди толстых объектов». Журнал алгоритмов . 21 (3): 629. doi : 10.1006/jagm.1996.0063 . hdl : 1874/17327 .
^ Раджан, В.Т. (1994). «Оптимальность триангуляции Делоне в $\mathbb {R} ^{d}$ « . Дискретная и вычислительная геометрия . 12 (2): 189–202. doi : 10.1007/BF02574375 . MR 1283887 .
^ Вайсштейн, Эрик В. «Инрадиус» . Математический мир . Проверено 28 сентября 2014 г.
^ См. график: https://www.desmos.com/calculator/fhfqju02sn .
^ Марк де Берг; Онак, Кшиштоф; Сидиропулос, Анастасиос (2010). «Толстые многоугольные разбиения с применением к визуализации и встраиваниям». Журнал вычислительной геометрии . 4 . arXiv : 1009.1866 . дои : 10.20382/jocg.v4i1a9 . S2CID 15245776 .
^ Де Берг, Марк; Шпекманн, Беттина ; Ван дер Вил, Винсент (2014). «Древовидные карты с ограниченным соотношением сторон». Вычислительная геометрия . 47 (6): 683. arXiv : 1012.1749 . дои : 10.1016/j.comgeo.2013.12.008 . S2CID 12973376 . . Версия конференции: Выпуклые древовидные карты с ограниченным соотношением сторон (PDF) . ЕвроКГ. 2011.
^ Сегал-Халеви, Эрель; Ницан, Шмуэль; хасидим, Авинатан; Ауманн, Йонатан (2017). «Честно и справедливо: разрезание торта в двух измерениях». Журнал математической экономики . 70 : 1–28. arXiv : 1409.4511 . дои : 10.1016/j.jmateco.2017.01.007 . S2CID 1278209 .

[1] Кац, MJ (1997). «3D-съемка вертикальными лучами и 2D-точечное наложение, поиск дальности и дуговая стрельба среди выпуклых толстых объектов» (PDF) . Вычислительная геометрия . 8 (6): 299–316. дои : 10.1016/s0925-7721(96)00027-2 . S2CID 122806176 . , Агарвал, ПК; Кац, MJ; Шарир, М. (1995). «Вычисление порядков глубины для толстых объектов и связанные с этим проблемы» . Вычислительная геометрия . 5 (4): 187. дои : 10.1016/0925-7721(95)00005-8 .

[EfratEtAl2000-2] Перейти обратно: ^а ^б ^с Эфрат, А.; Кац, MJ; Нильсен, Ф.; Шарир, М. (2000). «Динамические структуры данных для толстых объектов и их приложений» . Вычислительная геометрия . 15 (4): 215. дои : 10.1016/s0925-7721(99)00059-0 .

[vanderStappenEtAl1993-3] Перейти обратно: ^а ^б ^с ^д ^и ^ж Ван дер Стаппен, AF; Гальперин, Д.; Овермарс, Миннесота (1993). «Сложность свободного пространства для робота, движущегося среди толстых препятствий». Вычислительная геометрия . 3 (6): 353. doi : 10.1016/0925-7721(93)90007-s . hdl : 1874/16650 .

[4] Берг, М.; Грут, М.; Овермарс, М. (1994). «Новые результаты о разбиениях двоичного пространства на плоскости (расширенный тезис)». Теория алгоритмов — SWAT '94 . Конспекты лекций по информатике. Том. 824. с. 61. дои : 10.1007/3-540-58218-5_6 . ISBN 978-3-540-58218-2 . , Ван дер Стаппен, AF; Овермарс, Миннесота (1994). «Планирование движения среди толстых препятствий (расширенный реферат)». Материалы десятого ежегодного симпозиума по вычислительной геометрии - SCG '94 . п. 31. дои : 10.1145/177424.177453 . ISBN 978-0897916486 . S2CID 152761 . , Овермарс, Миннесота (1992). «Расположение точек в жировых подразделениях». Письма об обработке информации (представленная рукопись). 44 (5): 261–265. дои : 10.1016/0020-0190(92)90211-д . hdl : 1874/17965 . , Овермарс, Миннесота; Ван дер Стаппен, ФА (1996). «Поиск дальности и расположение точек среди толстых объектов». Журнал алгоритмов . 21 (3): 629. doi : 10.1006/jagm.1996.0063 . hdl : 1874/17327 .

[5] Раджан, В.Т. (1994). «Оптимальность триангуляции Делоне в $\mathbb {R} ^{d}$ « . Дискретная и вычислительная геометрия . 12 (2): 189–202. doi : 10.1007/BF02574375 . MR 1283887 .

[6] Вайсштейн, Эрик В. «Инрадиус» . Математический мир . Проверено 28 сентября 2014 г.

[7] См. график: https://www.desmos.com/calculator/fhfqju02sn .

[bos13-8] Марк де Берг; Онак, Кшиштоф; Сидиропулос, Анастасиос (2010). «Толстые многоугольные разбиения с применением к визуализации и встраиваниям». Журнал вычислительной геометрии . 4 . arXiv : 1009.1866 . дои : 10.20382/jocg.v4i1a9 . S2CID 15245776 .

[dsv2-9] Де Берг, Марк; Шпекманн, Беттина ; Ван дер Вил, Винсент (2014). «Древовидные карты с ограниченным соотношением сторон». Вычислительная геометрия . 47 (6): 683. arXiv : 1012.1749 . дои : 10.1016/j.comgeo.2013.12.008 . S2CID 12973376 . . Версия конференции: Выпуклые древовидные карты с ограниченным соотношением сторон (PDF) . ЕвроКГ. 2011.

[10] Сегал-Халеви, Эрель; Ницан, Шмуэль; хасидим, Авинатан; Ауманн, Йонатан (2017). «Честно и справедливо: разрезание торта в двух измерениях». Журнал математической экономики . 70 : 1–28. arXiv : 1409.4511 . дои : 10.1016/j.jmateco.2017.01.007 . S2CID 1278209 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]