{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:06Z","timestamp":1759638966901},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,12,26]],"date-time":"2017-12-26T00:00:00Z","timestamp":1514246400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2018,3]]},"DOI":"10.1007\/s00454-017-9958-8","type":"journal-article","created":{"date-parts":[[2017,12,26]],"date-time":"2017-12-26T14:55:22Z","timestamp":1514300122000},"page":"253-292","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Computation of Zone and Double Zone Diagrams"],"prefix":"10.1007","volume":"59","author":[{"given":"Daniel","family":"Reem","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,12,26]]},"reference":[{"key":"9958_CR1","doi-asserted-by":"crossref","unstructured":"Asano, T., Kirkpatrick, D.: Distance trisector curves in regular convex distance metrics. In: Gavrilova, M.L. (ed.) Proceedings of the 3rd International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2006), pp. 8\u201317. IEEE Computer Society, Los Alamitos (2006)","DOI":"10.1109\/ISVD.2006.21"},{"key":"9958_CR2","doi-asserted-by":"crossref","unstructured":"Asano, T., Matou\u0161ek, J., Tokuyama, T.: Zone diagrams: existence, uniqueness, and algorithmic challenge. SIAM J. Comput. 37(4), 1182\u20131198 (2007). A preliminary version in SODA 2007, pp. 756\u2013765","DOI":"10.1137\/06067095X"},{"key":"9958_CR3","unstructured":"Asano, T., Tokuyama, T.: Drawing equally-spaced curves between two points. In: Abstracts of the 14th Annual Workshop on Computational Geometry with a Focus on Open Problems, pp. 24\u201325. Massachusetts Institute of Technology, Cambridge (2004)"},{"key":"9958_CR4","unstructured":"Asano, T., Matou\u0161ek, J., Tokuyama, T.: The distance trisector curve. Adv. Math. 212(1), 338\u2013360 (2007). A preliminary version in STOC 2006, pp. 336\u2013343"},{"issue":"3","key":"9958_CR5","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1145\/116873.116880","volume":"23","author":"F Aurenhammer","year":"1991","unstructured":"Aurenhammer, F.: Voronoi diagrams\u2014a survey of a fundamental geometric data structure. ACM Comput. Surv. 23(3), 345\u2013405 (1991)","journal-title":"ACM Comput. Surv."},{"key":"9958_CR6","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/B978-044482537-7\/50006-1","volume-title":"Handbook of Computational Geometry","author":"F Aurenhammer","year":"2000","unstructured":"Aurenhammer, F., Klein, R.: Voronoi diagrams. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, pp. 201\u2013290. North-Holland, Amsterdam (2000)"},{"key":"9958_CR7","doi-asserted-by":"crossref","unstructured":"Ba\u010d\u00e1k, M.: Convex Analysis and Optimization in Hadamard Spaces. De Gruyter Series in Nonlinear Analysis and Applications, vol. 22. De Gruyter, Berlin (2014)","DOI":"10.1515\/9783110361629"},{"key":"9958_CR8","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M Berg de","year":"2008","unstructured":"de Berg, M., Cheong, O., van Kreveld, M., Overmars, M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"9958_CR9","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1109\/ISVD.2010.10","volume-title":"Proceedings of the 7th International Symposium on Voronoi Diagrams in Science and Engineering","author":"SC Biasi de","year":"2010","unstructured":"de Biasi, S.C., Kalantari, B., Kalantari, I.: Maximal zone diagrams and their computation. In: Mostafavi, M.A. (ed.) Proceedings of the 7th International Symposium on Voronoi Diagrams in Science and Engineering, pp. 171\u2013180. IEEE Computer Society, Los Alamitos (2010)"},{"key":"9958_CR10","doi-asserted-by":"crossref","unstructured":"de\u00a0Biasi, S.C., Kalantari, B., Kalantari, I.: Mollified zone diagrams and their computation. In: Gavrilova, M.L. et al. (eds.) Transactions on Computational Science XIV. Lecture Notes in Computer Science, vol. 6970, pp. 31\u201359. Springer, Heidelberg (2011). A preliminary version in ISVD 2010, pp. 171\u2013180","DOI":"10.1007\/978-3-642-25249-5_2"},{"key":"9958_CR11","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139172998","volume-title":"Algorithmic Geometry","author":"J-D Boissonnat","year":"1998","unstructured":"Boissonnat, J.-D., Yvinec, M.: Algorithmic Geometry. Cambridge University Press, Cambridge (1998)"},{"key":"9958_CR12","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-70914-7","volume-title":"Functional Analysis, Sobolev Spaces and Partial Differential Equations. Universitext","author":"H Brezis","year":"2011","unstructured":"Brezis, H.: Functional Analysis, Sobolev Spaces and Partial Differential Equations. Universitext. Springer, New York (2011)"},{"key":"9958_CR13","volume-title":"The Geometry of Geodesics","author":"H Busemann","year":"1955","unstructured":"Busemann, H.: The Geometry of Geodesics. Academic Press, New York (1955)"},{"key":"9958_CR14","unstructured":"Chun, J., Okada, Y., Tokuyama, T.: Distance trisector of a segment and a point. Interdiscip. Inf. Sci. 16(1), 119\u2013125 (2010). A preliminary version in ISVD 2007, pp. 66\u201373"},{"key":"9958_CR15","doi-asserted-by":"crossref","first-page":"66","DOI":"10.1109\/ISVD.2007.19","volume-title":"Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007)","author":"J Chun","year":"2007","unstructured":"Chun, J., Okada, Y., Tokuyama, T.: Distance trisector of segments and zone diagram of segments in a plane. In: Gold, C.M. (ed.) Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2007), pp. 66\u201373. IEEE Computer Society, Los Alamitos (2007)"},{"issue":"1","key":"9958_CR16","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1142\/S0218195996000046","volume":"6","author":"AG Corbalan","year":"1996","unstructured":"Corbalan, A.G., Mazon, M., Recio, T.: Geometry of bisectors for strictly convex distances. Int. J. Comput. Geom. Appl. 6(1), 45\u201358 (1996)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"9958_CR17","doi-asserted-by":"crossref","unstructured":"Corbalan, A., Mazon, M., Recio, T., Santos, F.: On the topological shape of planar Voronoi diagrams. In: Proceedings of the 9th Annual Symposium on Computational Geometry (SoCG 1993), pp. 109\u2013115. ACM, New York (1993)","DOI":"10.1145\/160985.161006"},{"key":"9958_CR18","unstructured":"Courant, R., Hilbert, D.: Methods of Mathematical Physics. Vol. II: Partial Differential Equations. Interscience Publishers, New York (1962)"},{"key":"9958_CR19","volume-title":"Finite Model Theory. Perspectives in Mathematical Logic","author":"H-D Ebbinghaus","year":"1999","unstructured":"Ebbinghaus, H.-D., Flum, J.: Finite Model Theory. Perspectives in Mathematical Logic, 2nd edn. Springer, Berlin (1999)","edition":"2"},{"key":"9958_CR20","doi-asserted-by":"crossref","unstructured":"Edelsbrunner, H.: Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science, vol. 10. Springer, Berlin (1987)","DOI":"10.1007\/978-3-642-61568-9"},{"key":"9958_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"612","DOI":"10.1007\/978-3-642-45030-3_57","volume-title":"Algorithms and Computation","author":"R Fraser","year":"2013","unstructured":"Fraser, R., He, M., Kawamura, A., L\u00f3pez-Ortiz, A., Munro, J.I., Nicholson, P.K.: The distance 4-sector of two points is unique. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) Algorithms and Computation. Lecture Notes in Computer Science, vol. 8283, pp. 612\u2013622. Springer, Heidelberg (2013)"},{"key":"9958_CR22","unstructured":"Goodman, J.E., O\u2019Rourke, J. (eds.): Handbook of Discrete and Computational Geometry. Discrete Mathematics and Its Applications (Boca Raton), 2nd edn. Chapman & Hall\/CRC, Boca Raton (2004)"},{"key":"9958_CR23","series-title":"An EATCS Series","volume-title":"Finite Model Theory and Its Applications. Texts in Theoretical Computer Science","author":"E Gr\u00e4del","year":"2007","unstructured":"Gr\u00e4del, E., Kolaitis, P.G., Libkin, L., Marx, M., Spencer, J., Vardi, M.Y., Venema, Y., Weinstein, S.: Finite Model Theory and Its Applications. Texts in Theoretical Computer Science. An EATCS Series. Springer, Berlin (2007)"},{"key":"9958_CR24","series-title":"Springer Monographs in Mathematics","doi-asserted-by":"crossref","DOI":"10.1007\/978-0-387-21593-8","volume-title":"Fixed Point Theory","author":"A Granas","year":"2003","unstructured":"Granas, A., Dugundji, J.: Fixed Point Theory. Springer Monographs in Mathematics. Springer, New York (2003)"},{"issue":"3","key":"9958_CR25","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1023\/A:1010611925838","volume":"89","author":"\u00c1G Horv\u00e1th","year":"2000","unstructured":"Horv\u00e1th, \u00c1.G.: On bisectors in Minkowski normed spaces. Acta Math. Hung. 89(3), 233\u2013246 (2000)","journal-title":"Acta Math. Hung."},{"issue":"1","key":"9958_CR26","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1216\/RMJ-2013-43-1-179","volume":"43","author":"\u00c1G Horv\u00e1th","year":"2013","unstructured":"Horv\u00e1th, \u00c1.G., Martini, H.: Bounded representation and radial projections of bisectors in normed spaces. Rocky Mt. J. Math. 43(1), 179\u2013191 (2013). arXiv:1002.0058","journal-title":"Rocky Mt. J. Math."},{"key":"9958_CR27","unstructured":"Imai, K., Kawamura, A., Matou\u0161ek, J., Reem, D., Tokuyama, T.: Distance $$k$$ k -sectors exist. Comput. Geom. 43(9), 713\u2013720 (2010). Preliminary versions in SoCG 2010, pp. 210\u2013215, arXiv:0912.4164"},{"key":"9958_CR28","doi-asserted-by":"crossref","unstructured":"Jost, J.: Riemannian Geometry and Geometric Analysis. Universitext, 6th edn. Springer, Heidelberg (2011)","DOI":"10.1007\/978-3-642-21298-7"},{"key":"9958_CR29","unstructured":"Kawamura, A., Matou\u0161ek, J., Tokuyama, T.: Zone diagrams in Euclidean spaces and in other normed spaces. Math. Ann. 354(4), 1201\u20131221 (2012). Preliminary versions in SoCG 2010, pp. 216\u2013221, arXiv:0912.3016"},{"key":"9958_CR30","doi-asserted-by":"crossref","unstructured":"Kirk, W.A., Sims, B. (eds.): Handbook of Metric Fixed Point Theory. Kluwer, Dordrecht (2001)","DOI":"10.1007\/978-94-017-1748-9"},{"key":"9958_CR31","first-page":"133","volume":"6","author":"B Knaster","year":"1928","unstructured":"Knaster, B.: Un th\u00e9or\u00e8me sur les fonctions d\u2019ensembles. Ann. Soc. Polon. Math. 6, 133\u2013134 (1928)","journal-title":"Ann. Soc. Polon. Math."},{"key":"9958_CR32","unstructured":"Kopeck\u00e1, E., Reem, D., Reich, S.: Zone diagrams in compact subsets of uniformly convex spaces. Isr. J. Math. 188, 1\u201323 (2012). Preliminary versions in arXiv:1002.3583 and CCCG 2010, pp. 17\u201320"},{"issue":"1","key":"9958_CR33","doi-asserted-by":"crossref","first-page":"9","DOI":"10.1007\/BF02187867","volume":"2","author":"D Leven","year":"1987","unstructured":"Leven, D., Sharir, M.: Planning a purely translational motion for a convex object in two-dimensional space using generalized Vorono\u012d diagrams. Discret. Comput. Geom. 2(1), 9\u201331 (1987)","journal-title":"Discret. Comput. Geom."},{"key":"9958_CR34","doi-asserted-by":"crossref","unstructured":"Lindenstrauss, J., Tzafriri, L.: Classical Banach Spaces, II: Function Spaces. Ergebnisse der Mathematik und ihrer Grenzgebiete, vol. 97. Springer, Berlin (1979)","DOI":"10.1007\/978-3-662-35347-9"},{"key":"9958_CR35","unstructured":"Ma, L.: Bisectors and Voronoi Diagrams for Convex Distance Functions. PhD thesis, Department of Computer Science, FernUniversit\u00e4t Hagen (2000)"},{"issue":"2","key":"9958_CR36","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1016\/S0723-0869(04)80009-4","volume":"22","author":"H Martini","year":"2004","unstructured":"Martini, H., Swanepoel, K.J.: The geometry of Minkowski spaces\u2014a survey. II. Expo. Math. 22(2), 93\u2013144 (2004)","journal-title":"Expo. Math."},{"key":"9958_CR37","doi-asserted-by":"crossref","unstructured":"Matou\u0161ek, J.: Lectures on Discrete Geometry. Graduate Texts in Mathematics, vol. 212. Springer, New York (2002)","DOI":"10.1007\/978-1-4613-0039-7"},{"key":"9958_CR38","unstructured":"Maz\u00f3n, M.L.: Diagrams de Voronoi en Caleidoscopios. PhD thesis, Universidad de Cantabria, Spain (1992)"},{"key":"9958_CR39","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1007\/s10711-013-9894-6","volume":"171","author":"J Monterde","year":"2014","unstructured":"Monterde, J., Ongay, F.: The distance trisector curve is transcendental. Geom. Dedicata 171, 187\u2013201 (2014)","journal-title":"Geom. Dedicata"},{"key":"9958_CR40","volume-title":"Computational Geometry: An Introduction Through Randomized Algorithms","author":"K Mulmuley","year":"1994","unstructured":"Mulmuley, K.: Computational Geometry: An Introduction Through Randomized Algorithms. Prentice-Hall, Englewood Cliffs (1994)"},{"key":"9958_CR41","series-title":"Wiley Series in Probability and Statistics","doi-asserted-by":"crossref","DOI":"10.1002\/9780470317013","volume-title":"Spatial Tessellations: Concepts and Applications of Voronoi Diagrams","author":"A Okabe","year":"2000","unstructured":"Okabe, A., Boots, B., Sugihara, K., Chiu, S.N.: Spatial Tessellations: Concepts and Applications of Voronoi Diagrams. Wiley Series in Probability and Statistics, 2nd edn. Wiley, Chichester (2000)","edition":"2"},{"key":"9958_CR42","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511801228","volume-title":"An Introduction to Partial Differential Equations","author":"Y Pinchover","year":"2005","unstructured":"Pinchover, Y., Rubinstein, J.: An Introduction to Partial Differential Equations. Cambridge University Press, Cambridge (2005)"},{"issue":"1","key":"9958_CR43","doi-asserted-by":"crossref","first-page":"18","DOI":"10.4169\/amer.math.monthly.121.01.018","volume":"121","author":"M Ponce","year":"2014","unstructured":"Ponce, M., Santib\u00e1\u00f1ez, P.: On equidistant sets and generalized conics: the old and the new. Am. Math. Mon. 121(1), 18\u201332 (2014)","journal-title":"Am. Math. Mon."},{"key":"9958_CR44","doi-asserted-by":"crossref","first-page":"93","DOI":"10.1007\/978-94-017-1748-9_4","volume-title":"Handbook of Fixed Point Theory","author":"S Prus","year":"2001","unstructured":"Prus, S.: Geometrical background of metric fixed point theory. In: Kirk, W.A., Sims, B. (eds.) Handbook of Fixed Point Theory, pp. 93\u2013132. Kluwer, Dordrecht (2001)"},{"key":"9958_CR45","doi-asserted-by":"crossref","first-page":"144","DOI":"10.1109\/ISVD.2009.23","volume-title":"Proceedings of the 6th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2009)","author":"D Reem","year":"2009","unstructured":"Reem, D.: An algorithm for computing Voronoi diagrams of general generators in general normed spaces. In: Anton, F. (ed.) Proceedings of the 6th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2009), pp. 144\u2013152. IEEE Computer Society, Los Alamitos (2009)"},{"key":"9958_CR46","unstructured":"Reem, D.: Voronoi and Zone Diagrams. PhD thesis, The Technion, Haifa (2010)"},{"key":"9958_CR47","unstructured":"Reem, D.: The geometric stability of Voronoi diagrams with respect to small changes of the sites. arXiv:1103.4125 (2011). Extended abstract in SoCG 2011, pp. 254\u2013263"},{"key":"9958_CR48","unstructured":"Reem, D.: The geometric stability of Voronoi diagrams in normed spaces which are not uniformly convex. arXiv:1212.1094 (2012) (current version: [v2], 29 Apr 2013)"},{"key":"9958_CR49","unstructured":"Reem, D.: On the possibility of simple parallel computing of Voronoi diagrams and Delaunay graphs. arXiv:1212.1095 (2012) (current version: [v3], 2 Apr 2015)"},{"key":"9958_CR50","unstructured":"Reem, D.: Topological properties of sets represented by an inequality involving distances. arXiv:1303.4733 (2013) (current version: [v2], 29 Apr 2013)"},{"key":"9958_CR51","unstructured":"Reem, D.: On the existence of a neutral region II: The implicit relation case. J. Nonlinear Convex Anal. 15(3), 525\u2013538 (2014). Preliminaries versions in arXiv:1208.3124 and ISVD 2012, pp. 80\u201383"},{"key":"9958_CR52","doi-asserted-by":"publisher","unstructured":"Reem, D.: Vdream: a computer program for the approximate computation of Voronoi and (double) zone diagrams of general sites and norms (2017). Zenodo (current version: [v3.2], 13 November 2017), available at: https:\/\/doi.org\/10.5281\/zenodo.1048204","DOI":"10.5281\/zenodo.1048204"},{"key":"9958_CR53","unstructured":"Reem, D., Reich, S.: Zone and double zone diagrams in abstract spaces. Colloq. Math. 115(1), 129\u2013145 (2009). A preliminary version in: arXiv:0708.2668"},{"issue":"6","key":"9958_CR54","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1016\/0362-546X(90)90058-O","volume":"15","author":"S Reich","year":"1990","unstructured":"Reich, S., Shafrir, I.: Nonexpansive iterations in hyperbolic spaces. Nonlinear Anal. 15(6), 537\u2013558 (1990)","journal-title":"Nonlinear Anal."},{"key":"9958_CR55","volume-title":"Davenport\u2013Schinzel Sequences and Their Geometric Applications","author":"M Sharir","year":"1995","unstructured":"Sharir, M., Agarwal, P.K.: Davenport\u2013Schinzel Sequences and Their Geometric Applications. Cambridge University Press, Cambridge (1995)"},{"issue":"2","key":"9958_CR56","doi-asserted-by":"crossref","first-page":"285","DOI":"10.2140\/pjm.1955.5.285","volume":"5","author":"A Tarski","year":"1955","unstructured":"Tarski, A.: A lattice-theoretical fixpoint theorem and its applications. Pac. J. Math. 5(2), 285\u2013309 (1955)","journal-title":"Pac. J. Math."},{"key":"9958_CR57","doi-asserted-by":"crossref","unstructured":"Walter, W.: Ordinary Differential Equations. Graduate Texts in Mathematics, vol. 182. Springer, New York (1998)","DOI":"10.1007\/978-1-4612-0601-9"},{"issue":"2","key":"9958_CR58","doi-asserted-by":"crossref","first-page":"446","DOI":"10.1090\/S0002-9939-1975-0355791-0","volume":"47","author":"JB Wilker","year":"1975","unstructured":"Wilker, J.B.: Equidistant sets and their connectivity properties. Proc. Am. Math. Soc. 47(2), 446\u2013452 (1975)","journal-title":"Proc. Am. Math. Soc."},{"key":"9958_CR59","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1109\/ISVD.2012.31","volume-title":"Proceedings of the 9th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2012)","author":"CK Yap","year":"2012","unstructured":"Yap, C.K., Sharma, V., Lien, J.-M.: Towards exact numerical Voronoi diagrams. In: Kalantari, B., Gavrilova, M.L. (eds.) Proceedings of the 9th International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2012), pp. 2\u201316. IEEE Computer Society, Los Alamitos (2012)"}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-017-9958-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9958-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9958-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,11]],"date-time":"2022-08-11T07:26:13Z","timestamp":1660202773000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-017-9958-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,12,26]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,3]]}},"alternative-id":["9958"],"URL":"https:\/\/doi.org\/10.1007\/s00454-017-9958-8","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,12,26]]}}}