In this paper are considered planar point sets generated by linear conditions, which are realized in rectangular or Manhattan metric. Linear conditions are those expressed by the finite sum of the products of distances by numerical coefficients. Finite sets of points and lines are considered as figures defining linear conditions. It has been shown that linear conditions can be defined relative to other planar figures: lines, polygons, etc. The design solutions of the following general geometric problem are considered: for a finite set of figures (points, line segments, polygons...) specified on a plane with a rectangular metric, which are in a common position, it is necessary to construct sets that satisfy any linear condition. The problems in which the given sets are point and segment ones have been considered in detail, and linear conditions are represented as a sum or as relations of distances. It is proved that solution result can be isolated points, broken lines, and areas on the plane. Sets of broken lines satisfying the given conditions form families of isolines for the given condition. An algorithm for building isoline families is presented. The algorithm is based on the Hanan lattice construction and the isolines behavior in each node and each sub-region of the lattice. For isoline families defined by conditions for relation of distances, some of their properties allowing accelerate their construction process are proved. As an example for application of the described theory, the problem of plane partition into regions corresponding to a given set of points, lines and other figures is considered. The problem is generalized problem of Voronoi diagram construction, and considered in general formulation. It means the next: 1) the problem is considered in rectangular metric; 2) all given points may be integrated in various figures – separate points, line segments, triangles, quadrangles etc.; 3) the Voronoi diagram’s property of proximity is changed for property of proportionality. Have been represented examples for plane partition into regions, determined by two-point sets.
rectangular metric, distance, linear conditions, Hanan lattice, isolines family, plane partition, Voronoi diagram
1. Vyshnepolskii V.I., Salkov N.A., Zavarihina E.V. Geometricheskie mesta tochek, pavnootstoyaschih ot dvuh zadannyh geometricheskih figure. Chast 1. [Geometric location of points equidistant from two specified geometric shapes. Part 1]. Geometriya i grafika [Geometry and graphics]. 2017, V. 5, I. 3, pp. 21-35. DOIhttps://doi.org/10.12737/article_59bfa3beb72932.73328568. (in Russian)
2. Vyshnepolskii V.I., Zavarihina E.V., Dallakyan Geometricheskie mesta tochek, pavnootstoyaschih ot dvuh zadannyh geometricheskih figure. Chast 2: geometricheskie mesta tochek, ravnoudalennyh ot tochki i konicheskoi poverhnosti. [Geometric location of points equidistant from two specified geometric shapes. Part 2]. Geometriya i grafika [Geometry and graphics]. 2017, V. 5, I. 4, pp. 15-23. DOIhttps://doi.org/10.12737/article_5a17f9503d6f40.18070994. (in Russian)
3. Vyshnepolskii V.I., Kirshanov K.A., Egiazaryan K.T. Geometricheskie mesta tochek, pavnootstoyaschih ot dvuh zadannyh geometricheskih figure. Chast 3. [Geometric location of points equidistant from two specified geometric shapes. Part 3]. Geometriya i grafika [Geometry and graphics]. 2018, V. 6, I. 4, pp. 3-19. DOIhttps://doi.org/10.12737/article_5c21f207bfd6e4.78537377. (in Russian)
4. Glogovskii V.V. Analogi conik v metrike Lp. [Analogy of conics in metrics Lp]. Prikladnaya geometriya i ingenernaya graphica [Applied geometry and engineering graphics]. 1978, V. 25, pp. 34-37. (in Russian)
5. Glogovskii V.V. Analogi conik v metrike Lp (Chast II). [Analogy of conics in metrics Lp. Part 2]. Prikladnaya geometriya i ingenernaya graphica [Applied geometry and engineering graphics]. 1978, V. 26, pp. 78-82. (in Russian)
6. Grafskii O.A., Ponomarchuk Yu.V., Holodolov A.A. Geometriya elektrostaticheskih polei [Geometry of electrostatic fields]. Geometriya i grafika [Geometry and graphics]. 2018, V. 6, I. 1, pp. 10-19. DOI:https://doi.org/10.12737/article_5ad085a6d75bb5.99078854. (in Russian)
7. Guseinov H.G., Moiseev A.N., Ushakov V.N. Ob approximacii oblastei dostijimosty upravlyaemih system [About approximation of achievable regions of guided systems]. PMM [PMM]. 1998, V. 62, I. 2, pp. 179-187. (in Russian)
8. Zikratova I.A., Shago F.N., Gurtov A.V., Ivaninskaya I.I. Optimizaciya zoni pokritiya seti sotovoi svyazi na osnove matematicheskogo programmirovaniya. [Optimization of honeycomb communication zones of covering by mathematic programming]. Nauch.-techn. Vestnik informacionnih technologii, mechaniki i optiki [Scientific and technical Bulletin of information technology, mechanics and optics]. 2015, V. 15, I. 2, pp. 313-321. (in Russian)
9. Zinoviev V.G. Strukturno-descriptivnii method konturnoi obrabotki opticheskih izobrajenii. [Structure-descriptive method of contours processing of optical images]. Opticheskii journal [Optical magazine]. 2000, V. 67, I. 7, pp. 33-37. (in Russian)
10. Kazakov A.L., Juravskaya M.A., Lempert A.A. Voprosi segmentacii logisticheskih platform v usloviyah stanovleniya regionalnoi logistiki [Logistic platform segmentation problems in region logistic formation]. Transport Urala [Transport of the Urals]. 2010, I. 4, pp. 17-20. (in Russian)
11. Kazakov A.L., Lempert A.A., Buharov D.S. K voprosu o segmentacii logisticheskih zon dlya obslujivaniya neprerivno raspredelennih potrebitelei [About segmentation of logistic zones for servicing the uninterrupted distributed consumers]. AiT [Ait]. 2013, I. 6, pp. 87-100. (in Russian)
12. Krivulin N.K., Plotnikov P.V. Ob algebraicheskom reshenii zadachi Rowlsa o razmeschenii na ploskosti s priamougolnoi metrikoi [About algebraic solution of Rowls problem of arrangement on the plane with orthogonal metrics]. Vestnik Sankt-Peterburgskogo universiteta. Seriya 1. Mathematika, mechanika, astronomiya [Bulletin of St. Petersburg University. Series 1. Mathematics, Mechanics. Astronomy]. 2015, V. 2, I. 2, pp. 194-201. (in Russian)
13. Ligun A.A., Shumeiko A.A., Korotkov V.S. Identifikcaciya slojnih ploskih konturov detalei v usloviyah avtomatizirovannogo proizvodstva. [Identification of complicated plane contours of details in automated production]. Nauka - proizvodstvu [Science - Production]. Kiev, 1991, pp. 306-311. (in Russian)
14. Panchuk K. L., Myasoedova T. M., Krisova I. V. Geometricheskaya model generatsii konturno-parallelnih linyi dlya avtomatizirovannogo rascheya traektorii rejucshego instrumenta [Geometric model of contour-parallel lines generation for automatic calculation of cutting instrument trajectory]. Geometriya i grafika [Geometry and graphics]. 2019, V. 7, I. 1, pp. 3-13. DOI:https://doi.org/10.12737/article_5c92012c51bba1.17153893. (in Russian)
15. Preparata F., Sheimos M. Vichislitelnaya geometria [Computational geometry]. Moscow, Mir Publ., 1989. 478 p. (in Russian)
16. Romanova V. A. Vizualizatsiya pravilnih mnogogrannikov v processe ih obrazovaniya. [Visualization of regular polyhedrons in its generation process]. Geometriya i grafika [Geometry and graphics]. 2019, V. 7, I. 1, pp. 55-67. DOI:https://doi.org/10.12737/article_5c91ffd0916d52.90296375. (in Russian)
17. Sosov E.N. Ob approksimativnih svoistvah mnojestv v specialnom metricheskom prostranstve. [About approximate properties of sets in the space with special metrics]. Izvestiya Vuzuv, Matematika [University News. Maths]. 1999, I. 6, pp. 81-84. (in Russian)
18. Starovoitov V.V. Lokalnie geometricheskie metodi tsifrivoi obrabotki i analiza izobrajenii [Local geometric methods of numerical processing and analyses of images]. Minsk, Institut tehnicheskoi kibernetiki NAN Belarusi Publ., 1997. 282 p. (in Russian)
19. Foks A., Pratt M. Vichislitelnaya geometria. Primenenie v proektirovanii i na proizvodstve [Computational geometry for design and manufacture]. Moscow, Mir Publ., 1982. 304 p. (in Russian)
20. Fu K. Strukturnie methodi v raspoznavanii obrazov [Structure methods in pattern analyses]. Moscow, Mir Publ., 1977, 320 p. (in Russian)
21. Shenen P., Kosnar M., Gardan I. Mathematika i SAPR [Mathematics and SAPR]. Moscow, Mir Publ., 1988. 204 p. (in Russian)
22. Shenen P., Kosnar M., Gardan I. Mathematika i SAPR [Mathematics and SAPR]. Moscow, Mir Publ., 1988. 264 p. (in Russian)
23. Yurkov V.Yu. Formalnoe predstavlenie uslovii incidentnosti v mnogomernih proektivnih prostranstvah. [Formal description of incidence conditions in multidimensional projective spaces]. Geometriya i grafika [Geometry and graphics]. 2016, V. 4, I. 4, pp. 3-13. DOIhttps://doi.org/10.12737/22838. (in Russian)
24. Edelsbrunner H., Ivanov A., Karasev R. Current open problems in discrete and computational geometry. Modelirovanie i analiz informacionnih system [Modeling and analysis of information systems]. 2012, V. 19, I. 5, pp. 5-17.
25. Francis R.L. A geometrical solution procedure for a rectilinear distance minimax location problem. AIIE Trans, 1972, V. 4, I.4, pp. 328-332.
26. Garey M. R., Graham R. L., Johnson D. S. The Complexity of Computing Steiner Minimal Trees. SIAM J. Appl. Math. - 1977. - V. 32. - I. 4. - pp. 835-859. DOI:https://doi.org/10.1137/0012072
27. Hanan M. On Steiner’s problem with rectilinear distance. SIAM J. Appl. Math. 1966, V. 14, I. 2, pp. 255-265. DOI:https://doi.org/10.1137/0114025
28. Krivulin N.K., Plotnikov P.V. On an algebraic solution of the Rawls location problem in the plane with rectilinear metric. Vestnik St. Petersburg University: Mathematics, 2015, V.48, I. 2, pp. 75-81.
29. Lee D. T. Two-Dimensional Voronoi Diagrams in Lp-metric. Journal of the Computing Machinery, 1980, V. 27, I. 4, pp. 187-195.
30. Overmars M.H., van Leeuwen J. Maintenance of configurations in the plane, J. Comput. and Syst. Sci., 1981, V. 23, pp. 166-204.
