В статье рассматриваются плоские точечные множества, порождаемые линейными условиями, которые реализуются в ортогональной метрике (метрике городских кварталов или манхэттенской метрике). Линейными условиями названы условия, выражающиеся конечной суммой произведений расстояний на числовые коэффициенты. В качестве фигур, определяющих линейные условия, рассматриваются конечные множества точек и прямых. Показано, что линейные условия могут быть определены относительно других плоских фигур: отрезков, многоугольников и т.п. Рассматриваются конструктивные решения следующей общей геометрической задачи: для заданного на плоскости с прямоугольной метрикой конечного множества фигур (точек, отрезков, многоугольников…), находящихся в общем положении, построить множества, удовлетворяющие какому-либо линейному условию. Подробно рассмотрены задачи, в которых заданные множества являются точечными и множествами отрезков, а линейные условия представляются в виде суммы или в виде отношений расстояний. Доказывается, что результатом решения могут быть изолированные точки, ломаные и области на плоскости. Множества ломаных, удовлетворяющих данным условиям, образуют семейства изолиний данного условия. Приведен алгоритм построения семейств изолиний. Алгоритм основан на построении решетки Ханана и поведения изолиний в каждом узле и каждой подобласти решетки. Для семейств изолиний, определенных условиями отношения расстояний, доказываются некоторые их свойства, позволяющие ускорить процесс их построения. В качестве примера применения описанной теории рассматривается задача разбиения плоскости на области, соответствующие заданному множеству точек, линий и других фигур. Задача является обобщением задачи построения диаграммы Вороного и рассматривается в общей постановке. Это означает следующее: 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:https://doi.org/10.12737/article_5c92012c51bba1.17153893
15. Препарата Ф. Вычислительная геометрия: Введение [Текст]: пер. с англ. / Ф. Препарата, М. Шеймос. - М.: Мир, 1989. - 478 с.
16. Романова В. А. Визуализация правильных многогранников в процессе их визуализации [Текст] / В.А. Романова // Геометрия и графика. - 2019. - Т. 7. - № 1. - С. 55-67. - DOI:https://doi.org/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:https://doi.org/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:https://doi.org/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.
