В статье рассматриваются плоские точечные множества, порождаемые линейными условиями, которые реализуются в ортогональной метрике (метрике городских кварталов или манхэттенской метрике). Линейными условиями названы условия, выражающиеся конечной суммой произведений расстояний на числовые коэффициенты. В качестве фигур, определяющих линейные условия, рассматриваются конечные множества точек и прямых. Показано, что линейные условия могут быть определены относительно других плоских фигур: отрезков, многоугольников и т.п. Рассматриваются конструктивные решения следующей общей геометрической задачи: для заданного на плоскости с прямоугольной метрикой конечного множества фигур (точек, отрезков, многоугольников…), находящихся в общем положении, построить множества, удовлетворяющие какому-либо линейному условию. Подробно рассмотрены задачи, в которых заданные множества являются точечными и множествами отрезков, а линейные условия представляются в виде суммы или в виде отношений расстояний. Доказывается, что результатом решения могут быть изолированные точки, ломаные и области на плоскости. Множества ломаных, удовлетворяющих данным условиям, образуют семейства изолиний данного условия. Приведен алгоритм построения семейств изолиний. Алгоритм основан на построении решетки Ханана и поведения изолиний в каждом узле и каждой подобласти решетки. Для семейств изолиний, определенных условиями отношения расстояний, доказываются некоторые их свойства, позволяющие ускорить процесс их построения. В качестве примера применения описанной теории рассматривается задача разбиения плоскости на области, соответствующие заданному множеству точек, линий и других фигур. Задача является обобщением задачи построения диаграммы Вороного и рассматривается в общей постановке. Это означает следующее: 1) она рассматривается в прямоугольной метрике; 2) заданные точки могут быть объединены в различные фигуры — отдельные точки, отрезки, треугольники, четырехугольники и т.д.; 3) свойство близости диаграммы Вороного заменяется свойством пропорциональности. Приведены примеры разбиения плоскости на области, определяемые двухточечными множествами.
прямоугольная метрика, расстояние, линейные условия, решетка Ханана, семейства изолиний; разбиение плоскости, диаграмма Вороного
1. Вышнепольский В.И. Геометрические места точек, равноотстоящих от двух заданных геометрических фигур. Часть 1 [Текст] / В.И. Вышнепольский, Н.А. Сальков, Е.В. Заварихина // Геометрия и графика. – 2017. – Т. 5. – № 3. – С. 21-35. – DOI https://doi.org/10.12737/article_59bfa3beb72932.73328568.
2. Вышнепольский В.И. Геометрические места точек, равноотстоящих от двух заданных геометрических фигур. Часть 2: геометрические места точек, равноудаленных от точки и конической поверхности [Текст] / В.И. Вышнепольский, Е.В. Заварихина, О.Л. Даллакян // Геометрия и графика. – 2017. – Т. 5. – № 4. – С. 15-23. – DOI https://doi.org/10.12737/article_5a17f9503d6f40.18070994.
3. Вышнепольский В.И. Геометрические места точек, равноотстоящих от двух заданных геометрических фигур. Часть 3 [Текст] / В.И. Вышнепольский, К.А. Киршанов, К.Т. Егиазарян // Геометрия и графика. – 2018. – Т. 6. – № 4. – С. 3-19. – DOI https://doi.org/10.12737/article_5c21f207bfd6e4.78537377.
4. Глоговский В.В. Аналоги коник в метрике Lp [Текст] / В.В. Глоговский // Прикладная геометрия и инженерная графика. – 1978. – Вып. 25. – С. 34-37.
5. Глоговский В.В. Аналоги коник в метрике Lp (Часть II) [Текст] / В.В. Глоговский // Прикладная геометрия и инженерная графика. – 1978. – Вып. 26. – С. 78-82.
6. Графский О.А. Геометрия электростатических полей [Текст] / О.А. Графский, Ю.В. Пономарчук, А.А. Холодилов // Геометрия и графика. – 2018. – Т. 6. – № 1. – С. 10-19. – DOI: doi.org/10.12737/article_5ad085a6d75bb5.99078854
7. Гусейнов Х.Г. Об аппроксимации областей достижимости управляемых систем [Текст] / Х.Г. Гусейнов, А.Н. Моисеев, В.Н. Ушаков // ПММ. – 1998. – Т. 62. – № 2. – С. 179-187.
8. Зикратова И.А. Оптимизация зоны покрытия сети сотовой связи на основе математического программирования [Текст]/ И.А. Зикратова, Ф.Н. Шаго, А.В. Гуртов, И.И. Иванинская // Науч.-техн. вестник информационных технологий, механики и оптики. – 2015. – Т. 15. – № 2. – С. 313-321.
9. Зиновьев В. Г. Структурно-дескриптивный метод контурной обработки оптических изображений [Текст] / В. Г. Зиновьев // Оптический журнал. – 2000. – Т. 67. – №.7. – С. 33-37.
10. Казаков А.Л. Вопросы сегментации логистических платформ в условиях становления региональной логистики [Текст] / А.Л. Казаков, М.А. Журавская, А.А. Лемперт // Транспорт Урала. – 2010. – № 4. – С. 17-20.
11. Казаков А.Л. К вопросу о сегментации логистических зон для обслуживания непрерывно распределенных потребителей [Текст]/ А.Л. Казаков, А.А. Лемперт, Д.С. Бухаров // АиТ. – 2013. – № 6. – С. 87-100.
12. Кривулин Н.К. Об алгебраическом решении задачи Ролса о размещении на плоскости с прямоугольной метрикой / Н.К. Кривулин, П.В. Плотников // Вестник Санкт-Петербургского университета. Серия 1. Математика, Механика. Астрономия. – 2015. – Т. 2. – № 2. – С. 194-201.
13. Лигун А.А. Идентификация сложных плоских контуров деталей в условиях автоматизированного производства [Текст] / А.А. Лигун, А.А. Шумейко, В.С. Коротков // Наука – производству. – Киев, 1991. – С. 306-311.
14. Панчук К.Л. Геометрическая модель генерации семейства контурно-параллельных линий для автоматизированного расчета траектории режущего инструмента [Текст] / К.Л.Панчук, Т.М. Мясоедова, И.В. Крысова // Геометрия и графика. – 2019. – Т.7. – № 1. – С. 3-13. – DOI: 10.12737/article_5c92012c51bba1.17153893
15. Препарата Ф. Вычислительная геометрия: Введение [Текст]: пер. с англ. / Ф. Препарата, М. Шеймос. – М.: Мир, 1989. – 478 с.
16. Романова В. А. Визуализация правильных многогранников в процессе их визуализации [Текст] / В.А. Романова // Геометрия и графика. – 2019. – Т. 7. – № 1. – С. 55-67. – DOI: 10.12737/article_5c91ffd0916d52.90296375
17. Сосов Е.Н. Об аппроксимативных свойствах множеств в специальном метрическом пространстве [Текст] / Е.Н. Сосов // Изв. Вузов. Математика. – 1999. – № 6. – С. 81-84.
18. Старовойтов В.В. Локальные геометрические методы цифровой обработки и анализа изображений [Текст] / В.В. Старовойтов. – Минск: Институт технической кибернетики НАН Беларуси, 1997. – 282 с.
19. Фокс А. Вычислительная геометрия. Применение в проектировании и на производстве [Текст]: пер. с англ. / А. Фокс, М. Пратт. – М.: Мир, 1982. – 304 с.
20. Фу К. Структурные методы в распознавании образов [Текст] / К. Фу. – М.: Мир, 1977. – 320 с.
21. Шенен П. Математика и САПР [Текст]: пер. с франц. В 2-х кн. Кн. 1 / П. Шенен, М. Коснар, И. Гардан и др. – М.: Мир, 1988. – 204 с.
22. Шенен П. Математика и САПР [Текст]: пер. с франц. В 2-х кн. Кн. 2 / П. Шенен, М. Коснар, И. Гардан и др. – М.: Мир, 1988. – 264 с.
23. Юрков В.Ю. Формальное представление условий инцидентности в многомерных проективных пространствах [Текст] / В.Ю. Юрков // Геометрия и графика. – 2016. – Т. 4. – № 4. – С. 3-13. – DOI https://doi.org/10.12737/22838
24. Edelsbrunner H. Current open problems in discrete and computational geometry [Текст] / H. Edelsbrunner, A. Ivanov, R. Karasev // Моделирование и анализ информационных систем. – 2012. – Т.19. – № 5. – С. 5-17.
25. Francis R.L. A geometrical solution procedure for a rectilinear distance minimax location problem [Текст] / R.L. Francis // AIIE Trans. – 1972. – V. 4. – №4. – P. 328 – 332.
26. Garey M. R. The Complexity of Computing Steiner Minimal Trees [Текст] / M. R. Garey, R. L. Graham, D. S. Johnson // SIAM J. Appl. Math. – 1977. – V. 32. – no. 4. – P. 835 – 859. DOI: 10.1137/0012072
27. Hanan M. On Steiner’s problem with rectilinear distance [Текст] / M. Hanan // SIAM J. Appl. Math. – 1966. – V. 14. – № 2. – P. 255 – 265. DOI: 10.1137/0114025
28. Krivulin N.K. On an algebraic solution of the Rawls location problem in the plane with rectilinear metric [Текст] / N.K. Krivulin, P.V. Plotnikov // Vestnik St. Petersburg University: Mathematics. – 2015. – Vol.48. – № 2. – P. 75 – 81.
29. Lee D. T. Two-Dimensional Voronoi Diagrams in Lp-metric [Текст] / D.T. Lee // Journal of the Computing Machinery. – 1980. – V. 27. – № 4. – P. 187 – 195.
30. Overmars M.H. Maintenance of configurations in the plane [Текст]/ M.H. Overmars, J. van Leeuwen // J. Comput. and Syst. Sci. // 1981. – V. 23. – P. 166 – 204.
