Построение цифровой модели местности для территории с равнинным рельефом

При проектировании размещения коммуникаций на неоднородной территории используется цифровая модель местности – конечное множество точек территории, в которых заданы характеристики, определяющие затраты на строительство. Цифровая модель местности рассматривается как граф, и трасса коммуникации ищется в виде кратчайшего пути на этом графе. Статья посвящена исследованию близости таких трасс к оптимальным трассам в непрерывном случае. На плоскости строится специальный граф, у которого локальная степень узла зависит от параметра, формулируется правило, определяющее смежность узлов графа с использованием пар взаимно простых чисел; доказываются некоторые свойства кратчайших путей, дается оценка превышения длины кратчайшего пути над длиной соответствующего прямолинейного отрезка и оценка наибольшего удаления точек пути от точек отрезка.