Мощение
В математике грунтовое покрытие собой набор непересекающихся блоков R⁺ представляет . Подмножество X что из Rⁿ можно аппроксимировать двумя подмощениями X⁻ и X⁺ такими,
Икс⁻ ⊂ Икс ⊂ Икс⁺ .
В R¹ прямоугольники представляют собой отрезки прямых, в R² — прямоугольники, а в Rⁿ — гиперпрямоугольники. Основание R² также может представлять собой « неправильную плитку из прямоугольников», если в нем нет отверстий.
Преимущество ящиков заключается в том, что ими очень легко манипулировать компьютеры, поскольку они составляют основу интервального анализа . Многие интервальные алгоритмы естественным образом предоставляют решения, которые представляют собой обычные грунтовые покрытия. [1]
В вычислениях хорошо известным применением подмощения в R² является структура данных Quadtree . В контексте трассировки изображений и других приложениях важно рассматривать X⁻ как топологическую внутреннюю часть , как показано на рисунке.
Пример
[ редактировать ]Три рисунка справа ниже показывают приближение набора
Икс знак равно {( Икс 1 , Икс 2 ) ∈ р 2 | х 2
1 + х 2
2 + грех( х 1 + х 2 ) ∈ [4,9]}
с разной точностью. Набор X⁻ соответствует красным ящикам, а набор X⁺ содержит все красные и желтые ящики.
В сочетании с интервальными методами подмостки используются для аппроксимации набора решений нелинейных задач, таких как задачи инверсии множества . [2] Подмостки также можно использовать для доказательства того, что множество, определенное нелинейными неравенствами, является связным путем . [3] обеспечить топологические свойства таких множеств, [4] решить проблемы пианиста [5] или для реализации множества вычислений. [6]
Ссылки
[ редактировать ]- ^ Киффер, М.; Брамс, И.; Уолтер, Э.; Жолен, Л. (2001). «Расчет гарантированного набора с грунтовым покрытием» (PDF) . Научные вычисления, проверенные численные данные, интервальные методы . стр. 167–172. дои : 10.1007/978-1-4757-6484-0_14 . ISBN 978-1-4419-3376-8 .
- ^ Жолен, Люк; Уолтер, Эрик (1993). «Установите инверсию с помощью интервального анализа для нелинейной оценки с ограниченной ошибкой» (PDF) . Автоматика . 29 (4): 1053–1064. дои : 10.1016/0005-1098(93)90106-4 .
- ^ Делану, Н.; Жолен, Л.; Коттенсо, Б. (2005). «Использование интервальной арифметики для доказательства связности множества» (PDF) . Теоретическая информатика . 351 (1).
- ^ Делану, Н.; Жолен, Л.; Коттансо, Б. (2006). «Подсчет количества соединенных компонентов набора и его применение в робототехнике» (PDF) . Прикладные параллельные вычисления. Современное состояние научных вычислений . Конспекты лекций по информатике. Том. 3732. стр. 93–101. дои : 10.1007/11558958_11 . ISBN 978-3-540-29067-4 .
- ^ Жолен, Л. (2001). «Планирование пути с использованием интервалов и графиков» (PDF) . Надежные вычисления . 7 (1).
- ^ Киффер, М.; Жолен, Л.; Брамс, И.; Уолтер, Э. (2001). «Расчет гарантированного набора с грунтовым покрытием» (PDF) . Научные вычисления, проверенные численные данные, интервальные методы . В. Кремер и Дж. Гуденберг (редакторы), «Научные вычисления, проверенные числовые данные, интервальные методы», Kluwer Academic Publishers. стр. 167–178. дои : 10.1007/978-1-4757-6484-0_14 . ISBN 978-1-4419-3376-8 .