Связанные понятия
Медиана — вершина графа, у которой сумма кратчайших расстояний от неё до вершин графа минимальная возможная.
Геометрический остов (англ. geometric spanner) или t-остовной граф, или t-остов первоначально был введён как взвешенный граф на множестве точек в качестве вершин, для которого существует t-путь между любой парой вершин для фиксированного параметра t. t-Путь определяется как путь в графе с весом, не превосходящим в t раз пространственное расстояние между конечными точками. Параметр t называется коэффициентом растяжения остова.
Задача коммивояжёра (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в поиске самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. В условиях задачи указываются критерий выгодности маршрута (кратчайший, самый дешёвый, совокупный критерий и тому подобное) и соответствующие матрицы расстояний, стоимости и тому подобного. Как правило, указывается, что...
Зада́ча Кобо́на о треуго́льниках — нерешённая задача комбинаторной геометрии, сформулированная Кодзабуро Фудзмурой (яп. 藤村幸三郎 фудзимура ко:дзабуро:), известным также как Кобон. В задаче спрашивается, каково максимальное число N(k) неперекрывающихся треугольников, стороны которых принадлежат конфигурации k прямых. Вариант задачи рассматривается в проективной плоскости, а не в евклидовой плоскости, и в этом случае требуется, чтобы треугольники не пересекались другими прямыми конфигурации.
Парадокс береговой линии — противоречивое наблюдение в географических науках, связанное с невозможностью точно определить длину линии побережья из-за её фракталоподобных свойств. Первое задокументированное описание данного феномена было сделано Льюисом Ричардсоном; впоследствии оно было расширено Бенуа Мандельбротом.
Полигонометрия (от греч. polýgonos — многоугольный и …метрия) — один из методов определения взаимного положения точек земной поверхности для построения геодезических сетей, служащей основой топографических съёмок, планировки и строительства городов, перенесения проектов инженерных сооружений в натуру и т. п. Положения пунктов в принятой системе координат определяют путём измерения на местности длин линий, последовательно соединяющих эти пункты и образующих полигонометрический ход, и горизонтальных...
В теории графов графом единичных расстояний называется граф, образованный точками на евклидовой плоскости, при этом две вершины соединяются ребром если расстояние между ними равно в точности единице. Рёбра графа единичных расстояний иногда пересекаются, так что они не всегда планарны. Граф единичных расстояний без пересечений называется спичечным графом.
Подробнее: Граф единичных расстояний
Задача о самом широком пути — это задача нахождения пути между двумя выбранными вершинами во взвешенном графе, максимизирующего вес минимального по весу ребра графа (если рассматривать вес ребра как ширину дороги, то задача стоит в выборе самой широкой дороги, связывающей две вершины). Задача о самом широком пути известна также как задача об узком месте или задача о пути с максимальной пропускной способностью. Можно приспособить алгоритмы кратчайшего пути для вычисления пропускной способности путём...
В визуализации графов и геометрической теории графов число наклонов графа — это минимальное возможное число различных коэффициентов наклона рёбер в рисунке графа, в котором вершины представляются точками евклидовой плоскости, а рёбрами являются отрезки, которые не проходят через вершины, неинцидентные этим рёбрам.
Подробнее: Число наклонов графа
Граф ближайших соседей (ГБС) для множества P, состоящего из n объектов в метрическом пространстве (например, для множества точек на плоскости с евклидовой метрикой) — это ориентированный граф, вершинами которого служат элементы множества P, в котором существует ориентированное ребро из p в q, если q является ближайшим соседом p (т.е. расстояние от p до q не больше, чем от p до любого другого объекта из P).
Геометрический центр дискретного множества точек евклидова пространства (говоря статистическим языком — выборки) — это точка, в которой минимизируется сумма расстояний до точек множества. Геометрический центр обобщает медиану в математической статистике, которая минимизирует расстояния в одномерной выборке данных. Таким образом, геометрический центр отражает центральную тенденцию в пространствах высокой размерности. Понятие известно также по названиям 1-медиана , пространственная медиана, или точка...
Сфери́ческий сегме́нт — поверхность, часть сферы, отсекаемая от неё некоторой плоскостью. Плоскость отсекает два сегмента: меньший сегмент называется также сферическим кругом.
Путевая ширина известна также как интервальная толщина (на единицу меньше размера наибольшей клики интервального суперграфа графа G), величина вершинного разделения или вершинно-поисковое число.
Алгоритм Гилберта — Джонсона — Кёрти (англ. Gilbert — Johnson — Keerthi algorithm, сокращённо GJK) — алгоритм для определения минимального расстояния между двумя выпуклыми множествами (объектами). В отличие от многих других алгоритмов нахождения расстояния, GJK не требует, чтобы геометрические данные были сохранены в каком-либо специфическом формате. Вместо этого алгоритм GJK полностью полагается на носитель функции и итерационным методом (с помощью итераций) генерирует ближайшие симплексы для корректного...
Минимальное расстояние пересечения орбиты (англ. Minimum orbit intersection distance), параметр MOID — величина, используемая в астрономии для описания предполагаемых тесных сближений и соударений между астрономическими объектами. Определяется как расстояние между ближайшими точками оскулирующих орбит двух тел. Наиболее интересным является вопрос о возможности столкновения с Землёй. Параметры MOID относительно орбиты Земли обычно содержатся в базах данных комет и астероидов, таких как JPL Small-Body...
Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
Дистанционно-регулярный граф — регулярный граф такой, что для любых двух вершин v и w число вершин с расстоянием j от v и расстоянием k от w зависят только от j, k и i = d(v, w).
Задача Вебера обобщает поиск геометрической медианы, для которой цены перевозок полагаются равными для всех точек потребления, и задачу нахождения точки Ферма, геометрической медианы трёх точек. По этой причине задачу иногда называют задачей Ферма – Вебера, хотя то же самое имя используется и для задачи нахождения невзвешенной геометрической медианы. Задача Вебера, в свою очередь, обобщается задачей притяжения – отталкивания, которая позволяет отрицательные цены, так что для некоторых точек большее...
Связное доминирующее множество и остовное дерево с максимальной листвой являются двумя тесно связанными структурами, определёнными на неориентированном графе.
Теория размещения производства (теория локации) — учение размещения производственных сил на территории, является частью региональной экономики. Теория рассматривает вопросы, какая хозяйственная деятельность находится там, где и почему, и базируется на принципе, что фирмы выбирают месторасположения, которые будут максимизировать их прибыль, а частные лица выбирают те места, которые максимизируют их полезность.
Го́мановская траекто́рия — в небесной механике эллиптическая орбита, используемая для перехода между двумя другими орбитами, обычно находящимися в одной плоскости. В простейшем случае она пересекает эти две орбиты в апоцентре и перицентре. Орбитальный манёвр для перехода включает в себя 2 импульса работы двигателя на разгон — для входа на гомановскую траекторию и для схода с неё. Названа в честь немецкого учёного Вальтера Гомана, в 1925 году описавшего её в своей книге. На Гомана оказал большое влияние...
Практическая астрономия — один из разделов астрометрии, описывающий способы нахождения географических координат, определения координат небесных светил, исчисления точного времени, а также нахождения азимута.
Смещение Малмквиста (сдвиг Малмквиста) — эффект в наблюдательной астрономии, приводящий к преимущественному обнаружению объектов с высокой светимостью. Впервые данный эффект описал в 1922 году шведский астроном Гуннар Малмквист (1893–1982), подробно исследовавший данное явление в 1925 году. В статистике данное смещение является систематической ошибкой и влияет на результаты обзоров в выборках, ограниченных по видимой звёздной величине, в которые не попадают звёзды, видимые звёздные величины которых...
Задачи упаковки — это класс задач оптимизации в математике, в которых пытаются упаковать объекты в контейнеры. Цель упаковки — либо упаковать отдельный контейнер как можно плотнее, либо упаковать все объекты, использовав как можно меньше контейнеров. Многие из таких задач могут относиться к упаковке предметов в реальной жизни, вопросам складирования и транспортировки. Каждая задача упаковки имеет двойственную задачу о покрытии, в которой спрашивается, как много требуется некоторых предметов, чтобы...
В вычислительной геометрии и планировании движений роботов граф видимости — это граф взаимной видимости точек пространства, обычно для множества точек и преград на евклидовой плоскости. Любая вершина в графе представляет точку пространства, а любое ребро представляет прямую видимость между точками. То есть, если отрезок прямой, соединяющий две точки пространства, не проходит через какую-либо преграду, в графе будет нарисовано ребро. Если множество точек пространства лежит на прямой, их можно понимать...
Подробнее: Граф видимости
Коэффициент сетчатости — инвариант планарных графов, измеряющий число ограниченных граней графа по отношению к возможному числу граней других планарных графов с тем же числом вершин. Коэффициент принимает значения от 0 для деревьев до 1 для максимальных планарных графов.
Радиальная траектория — в астродинамике и небесной механике кеплерова орбита с нулевым угловым моментом. Два объекта, находящиеся на радиальной траектории, движутся по одной прямой линии.
Локсодрома или локсодромия (от греч. «loxodromie»: греч. «loxos» — «косой», «наклонный» и греч. «dromos» — «путь») — кривая на поверхности вращения, пересекающая все меридианы под постоянным углом, называемым локсодромическим путевым углом.
Гравитационная модель Рейли (закон Рейли розничного тяготения, модель Рейли-Конверса) — более крупные города притягивают большее количество покупателей, готовых преодолевать более дальнее расстояние до крупных торговых центров, а сила притяжения пропорциональна количеству населения или обороту местной торговли. Модель разработана в 1931 году профессором Техасского университета Уильямом Джоном Рейли (1899—1970) по аналогии с законом всемирного тяготения Ньютона на основе эмпирических исследований...
Задача о размещении объектов , известная также как анализ расположения оборудования или задача k-центра, — это ветвь исследования операций и вычислительной геометрии, исследующей оптимальное расположение объектов с целью минимизировать цены перевозок с учётом таких ограничений, как размещение опасных материалов вблизи жилищ. Техника применима также к кластерному анализу.
Зада́ча о кратча́йшем пути ́ — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов рёбер, составляющих путь.
Отклонение от круглости — геометрическая величина, численно равная наибольшему расстоянию от точек реального профиля до прилегающей окружности. Ранее использовался термин некруглость.
Время свободного падения — характерное время, которое потребуется телу для коллапса под действием силы тяготения, если никакие другие силы не противодействуют коллапсу. Играет важную роль при определении временных шкал ряда астрофизических процессов, таких как звездообразование, вспышки сверхновых звёзд.
Трилатерация (от лат. trilaterus — трёхсторонний) — метод определения положения геодезических пунктов путём построения на местности системы смежных треугольников, в которых измеряются длины их сторон.
Контактное число (иногда число Ньютона, в химии соответствует координационному числу) — максимальное количество шаров единичного радиуса, которые могут одновременно касаться одного такого же шара в n-мерном евклидовом пространстве (предполагается, что шары не проникают друг в друга, то есть объём пересечения любых двух шаров равен нулю).
В теории графов
паросочетание или независимое множество рёбер в графе — это набор попарно несмежных рёбер.
В теории графов рамочным графом называется вид неориентированного графа, который можно нарисовать на плоскости таким способом, что любая ограниченная грань является четырёхугольником и любая вершина с тремя и менее соседями инцидентна неограниченной грани.
Подробнее: Рамочный граф
Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза. Задача определения максимального разреза для графа известна как задача о максимальном разрезе.
В теории графов графом единичных кругов называется граф пересечений семейства единичных кругов на евклидовой плоскости. То есть мы образуем вершину для каждого круга и соединяем две вершины ребром, если соответствующие круги пересекаются.
Подробнее: Граф единичных кругов
Локальный уровень выброса является алгоритмом в выявлении аномалий, который предложили Маркус М. Бройниг, Ганс-Петер Кригель, Реймонд Т. Нг и Ёрг Сандер в 2000 году для нахождения аномальных точек данных путём измерения локального отклонения данной точки данных с учётом её соседей.
Геостациона́рная орби́та (ГСО) — круговая орбита, расположенная над экватором Земли (0° широты), находясь на которой, искусственный спутник обращается вокруг планеты с угловой скоростью, равной угловой скорости вращения Земли вокруг оси. В горизонтальной системе координат направление на спутник не изменяется ни по азимуту, ни по высоте над горизонтом — спутник как бы «висит» в небе неподвижно. Поэтому спутниковая антенна, однажды направленная на такой спутник, всё время остаётся направленной на него...
Универсальное множество точек порядка n — это множество S точек евклидовой плоскости со свойством, что любой планарный граф с n вершинами имеет рисунок с прямыми рёбрами, в котором все вершины располагаются в точках множества S.
Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций.
В теории графов
доминирующее множество для графа G = (V, E) — это подмножество D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D. Число доминирования γ(G) — это число вершин в минимальном доминирующем множестве G.
Сдвиг среднего значения — это непараметрическая техника анализа пространства признаков для определения местоположения максимума плотности вероятности, так называемый алгоритм поиска моды. Область применения техники — кластерный анализ в компьютерном зрении и обработке изображений.