Что такое искомая точка
Перейти к содержимому

Что такое искомая точка

  • автор:

Минимальная охватывающая окружность Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Гибадуллин Артур Амирзянович

В статье рассматривается алгоритм построения минимальной охватывающей окружности для заданного множества точек .

i Надоели баннеры? Вы всегда можете отключить рекламу.

Похожие темы научных работ по математике , автор научной работы — Гибадуллин Артур Амирзянович

Некоторые применения вычислительной геометрии к задачам линейного программирования
О двух подходах к решению одной классической задачи вычислительной геометрии

Применение системы Maple в процессе обучения различным подходам к решению задач вычислительной геометрии

Применение рандомизированного подхода в задаче обнаружения объекта на аэрофотоснимке
Генерация профилей масштабируемой модели рельефа
i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.
i Надоели баннеры? Вы всегда можете отключить рекламу.

Текст научной работы на тему «Минимальная охватывающая окружность»

Минимальная охватывающая окружность Г ибадуллин А. А.

Гибадуллин Артур Амирзянович / Gibadullin Artur Amirzyanovich — студент, кафедра физико-математического образования, факультет информационных технологий и математики,

Нижневартовский государственный университет, г. Нижневартовск

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

Ключевые слова: вычислительная математика, минимальная охватывающая

окружность, множество точек, геометрия.

Задача построения минимальной охватывающей окружности относится к вычислительной математике и заключается в том, чтобы построить окружность минимального радиуса, охватывающую произвольное конечное множество точек 2мерного евклидового пространства [1]. Впервые эта задача была поставлена английским математиком Джеймсом Джозефом Сильвестром в 1857 году [2]. Смысл ее в том, чтобы найти точку, расстояние от которого до наиболее удаленной от нее точки из предложенного множества точек будет минимальным. Искомая точка — это центр минимальной охватывающей окружности, радиус окружности — расстояние до наиболее удаленной от центра точки.

max ((xi-x)2+(yi-y)2) = r2, i=1..m, где m — количество заданных точек, xi и yi -координаты точек, r — радиус окружности, x и у — искомые координаты центра.

Она распространяется не только на точки двумерного пространства, но и на пространства больших размерностей, в таких случаях она переходит в задачу построения n-мерной сферы, охватывающей все предложенные точки [1].

В рассматриваемом нами двумерном случае она представляет собой задачу размещения. Она используется при строительстве коммуникаций. Например, когда нам нужно определить оптимальное расположение пожарной части или больницы, чтобы из них как можно быстрее добраться до всех зданий в рассматриваемом районе. К ней относится и «проблема бомбардировки», когда заданы мишени, которые нужно поразить одним снарядом, и необходимо определить место и радиус поражения, чтобы взрывная волна смогла достичь всех целей. Проблема минимальной охватывающей окружности помогает по разрушениям найти эпицентр землетрясения.

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

Рис. 1. Минимальная охватывающая окружность

НАУЧНЫЕ ИССЛЕДОВАНИЯ № 1. 2015 | 6 |

Задачу можно решить с помощью алгоритма линейной структуры. Следует учесть, что окружность задается максимум тремя точками, лежащими на ней, минимальная охватывающая окружность для заданного множества точек всегда уникальна. Алгоритмы ее поиска заключаются в подборе соответствующих окружностей заданных парами или триплетами точек и проверке принадлежности остальных точек кругам, ограниченным данными окружностями. Выполнение операций заканчивается, когда подбирается такая окружность, которая охватывает все точки. В одном из них берется множество точек, генерируется случайная перестановка из них. Сначала строится окружность, заданная первыми двумя точками этой перестановки, с центром посередине. Затем поочередно в окружность добавляется по одной точке, при этом проверяется их принадлежность кругу. Если вновь добавленная точка оказалась вне окружности, то строится новый круг, на границе которого лежит эта точка [3].

Другой алгоритм заключается в том, что изначально строится окружность, охватывающая все предложенные точки. На следующем шаге строится новая окружность с тем же самым центром, но включающая точку, наиболее удаленную от центра рассматриваемой окружности. Затем окружность уменьшается до тех пор, пока на границе не будут две точки, расстояние между которыми равно диаметру, либо как минимум три точки.

1. Elzinga J., Hearn D. W. (1972), «The minimum covering sphere problem», Management Science 19: 96-104, doi:10.1287/mnsc.19.1.96.

2. Sylvester J. J. (1857), «A question in the geometry of situation», Quarterly Journal of Mathematics 1: 79.

3. Mark de Berg, Otfried Cheong, Marc van Kreveld, Mark Overmars. Computational Geometry Algorithms and Applications, p. 86.

| 7 | НАУЧНЫЕ ИССЛЕДОВАНИЯ № 1.2015

Что обозначает слово «Искомая» в Геометрии!

Искомая? Та, которую ищут. Искомая величина — которую нужно найти, определить.

та же что и в жизни !!)) это та которую ищут .

Та которую мы искали или нашли

Похожие вопросы

Ваш браузер устарел

Мы постоянно добавляем новый функционал в основной интерфейс проекта. К сожалению, старые браузеры не в состоянии качественно работать с современными программными продуктами. Для корректной работы используйте последние версии браузеров Chrome, Mozilla Firefox, Opera, Microsoft Edge или установите браузер Atom.

Что такое искомая?определение

KuOV

Искомая величина — это величина, которую надо найти в задаче.
Например, в геометрических задачах искомой величиной может быть длина стороны треугольника, его площадь или угол.
Часто искомую величину обозначают переменной.

Новые вопросы в Геометрия

З вершини С прямого кута трикутника АВС проведено висоту СН. Знайдіть кут СВА,якщо кут АСН дорівнює 60⁰

допоможіть будь ласка

Терміново , допоможіть

ПОМОГИТЕ СРОЧНО. ​

Підготувати Цікаві факти про Теорему Піфагора своїми словами

Что такое искомая точка

Определение географических координат точки А.

Шаг 1. Наносим точку на карту и подписываем.

Шаг 2. Прикладываем прямоугольный треугольник к вертикальной рамке листа и проводим линию.

Шаг 3. Прикладываем прямоугольный треугольник к горизонтальной рамке листа и проводим линию.

Шаг 4. Определяем широту данной точки.

Шаг 5. Определяем долготу данной точки.

Шаг 6. Записываем координаты точки А: 56°3’ 40’’ — северной широты;

42°39’ 20’’ — восточной долготы.

Определение местоположения точки Б по известным географическим координатам.

Шаг 1. Записываем координаты точки Б: 56°16’45‘’- северной широты; 42°53’5‘’- восточной долготы.

Шаг 2. Определяем на рамке значение широты и отмечаем линию.

Шаг 3. Определяем на рамке значение долготы и отмечаем линию.

Шаг 4. Прикладываем прямоугольный треугольник последовательно к горизонтальной и вертикальной рамке листа и проводим линии.

Шаг 5. На месте пересечения линий искомая точка Б

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *