[{"author":[{"full_name":"Boissonnat, Jean-Daniel","first_name":"Jean-Daniel","last_name":"Boissonnat"},{"last_name":"Dyer","first_name":"Ramsay","full_name":"Dyer, Ramsay"},{"full_name":"Ghosh, Arijit","first_name":"Arijit","last_name":"Ghosh"},{"full_name":"Wintraecken, Mathijs","last_name":"Wintraecken","first_name":"Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87"}],"date_updated":"2023-08-01T12:47:32Z","date_created":"2023-01-16T10:04:06Z","volume":69,"acknowledgement":"This work has been funded by the European Research Council under the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). Arijit Ghosh is supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015). Part of this work was done when Arijit Ghosh was a Researcher at Max-Planck-Institute for Informatics, Germany, supported by the IndoGerman Max Planck Center for Computer Science (IMPECS). Mathijs Wintraecken also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 754411 and the Austrian Science Fund (FWF): M-3073. A part of the results described in this paper were presented at SoCG 2018 and in [3]. \r\nOpen access funding provided by the Austrian Science Fund (FWF).","year":"2023","publication_status":"published","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"file_date_updated":"2023-02-02T11:01:10Z","ec_funded":1,"license":"https://creativecommons.org/licenses/by/4.0/","doi":"10.1007/s00454-022-00431-7","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"isi":["000862193600001"]},"isi":1,"quality_controlled":"1","project":[{"grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"},{"name":"Learning and triangulating manifolds via collapses","_id":"fc390959-9c52-11eb-aca3-afa58bd282b2","grant_number":"M03073"}],"month":"01","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"oa_version":"Published Version","file":[{"date_updated":"2023-02-02T11:01:10Z","date_created":"2023-02-02T11:01:10Z","success":1,"checksum":"46352e0ee71e460848f88685ca852681","file_id":"12488","relation":"main_file","creator":"dernst","file_size":582850,"content_type":"application/pdf","file_name":"2023_DiscreteCompGeometry_Boissonnat.pdf","access_level":"open_access"}],"_id":"12287","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","ddc":["510"],"title":"Local criteria for triangulating general manifolds","status":"public","intvolume":" 69","abstract":[{"lang":"eng","text":"We present criteria for establishing a triangulation of a manifold. Given a manifold M, a simplicial complex A, and a map H from the underlying space of A to M, our criteria are presented in local coordinate charts for M, and ensure that H is a homeomorphism. These criteria do not require a differentiable structure, or even an explicit metric on M. No Delaunay property of A is assumed. The result provides a triangulation guarantee for algorithms that construct a simplicial complex by working in local coordinate patches. Because the criteria are easily verified in such a setting, they are expected to be of general use."}],"type":"journal_article","date_published":"2023-01-01T00:00:00Z","publication":"Discrete & Computational Geometry","citation":{"ama":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. Local criteria for triangulating general manifolds. Discrete & Computational Geometry. 2023;69:156-191. doi:10.1007/s00454-022-00431-7","ista":"Boissonnat J-D, Dyer R, Ghosh A, Wintraecken M. 2023. Local criteria for triangulating general manifolds. Discrete & Computational Geometry. 69, 156–191.","ieee":"J.-D. Boissonnat, R. Dyer, A. Ghosh, and M. Wintraecken, “Local criteria for triangulating general manifolds,” Discrete & Computational Geometry, vol. 69. Springer Nature, pp. 156–191, 2023.","apa":"Boissonnat, J.-D., Dyer, R., Ghosh, A., & Wintraecken, M. (2023). Local criteria for triangulating general manifolds. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00431-7","mla":"Boissonnat, Jean-Daniel, et al. “Local Criteria for Triangulating General Manifolds.” Discrete & Computational Geometry, vol. 69, Springer Nature, 2023, pp. 156–91, doi:10.1007/s00454-022-00431-7.","short":"J.-D. Boissonnat, R. Dyer, A. Ghosh, M. Wintraecken, Discrete & Computational Geometry 69 (2023) 156–191.","chicago":"Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, and Mathijs Wintraecken. “Local Criteria for Triangulating General Manifolds.” Discrete & Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-022-00431-7."},"article_type":"original","page":"156-191","day":"01","article_processing_charge":"No","has_accepted_license":"1","scopus_import":"1","keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"]},{"article_type":"original","page":"745–770","publication":"Discrete and Computational Geometry","citation":{"chicago":"Arroyo Guevara, Alan M, Fabian Klute, Irene Parada, Birgit Vogtenhuber, Raimund Seidel, and Tilo Wiedera. “Inserting One Edge into a Simple Drawing Is Hard.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-022-00394-9.","mla":"Arroyo Guevara, Alan M., et al. “Inserting One Edge into a Simple Drawing Is Hard.” Discrete and Computational Geometry, vol. 69, Springer Nature, 2023, pp. 745–770, doi:10.1007/s00454-022-00394-9.","short":"A.M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, T. Wiedera, Discrete and Computational Geometry 69 (2023) 745–770.","ista":"Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. 2023. Inserting one edge into a simple drawing is hard. Discrete and Computational Geometry. 69, 745–770.","apa":"Arroyo Guevara, A. M., Klute, F., Parada, I., Vogtenhuber, B., Seidel, R., & Wiedera, T. (2023). Inserting one edge into a simple drawing is hard. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00394-9","ieee":"A. M. Arroyo Guevara, F. Klute, I. Parada, B. Vogtenhuber, R. Seidel, and T. Wiedera, “Inserting one edge into a simple drawing is hard,” Discrete and Computational Geometry, vol. 69. Springer Nature, pp. 745–770, 2023.","ama":"Arroyo Guevara AM, Klute F, Parada I, Vogtenhuber B, Seidel R, Wiedera T. Inserting one edge into a simple drawing is hard. Discrete and Computational Geometry. 2023;69:745–770. doi:10.1007/s00454-022-00394-9"},"date_published":"2023-04-01T00:00:00Z","scopus_import":"1","day":"01","has_accepted_license":"1","article_processing_charge":"Yes (in subscription journal)","status":"public","ddc":["510"],"title":"Inserting one edge into a simple drawing is hard","intvolume":" 69","_id":"11999","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","file":[{"file_size":1002218,"content_type":"application/pdf","creator":"alisjak","access_level":"open_access","file_name":"2022_DiscreteandComputionalGeometry_Arroyo.pdf","checksum":"def7ae3b28d9fd6aec16450e40090302","success":1,"date_created":"2022-08-29T11:23:15Z","date_updated":"2022-08-29T11:23:15Z","relation":"main_file","file_id":"12006"}],"type":"journal_article","abstract":[{"text":"A simple drawing D(G) of a graph G is one where each pair of edges share at most one point: either a common endpoint or a proper crossing. An edge e in the complement of G can be inserted into D(G) if there exists a simple drawing of G+e extending D(G). As a result of Levi’s Enlargement Lemma, if a drawing is rectilinear (pseudolinear), that is, the edges can be extended into an arrangement of lines (pseudolines), then any edge in the complement of G can be inserted. In contrast, we show that it is NP-complete to decide whether one edge can be inserted into a simple drawing. This remains true even if we assume that the drawing is pseudocircular, that is, the edges can be extended to an arrangement of pseudocircles. On the positive side, we show that, given an arrangement of pseudocircles A and a pseudosegment σ, it can be decided in polynomial time whether there exists a pseudocircle Φσ extending σ for which A∪{Φσ} is again an arrangement of pseudocircles.","lang":"eng"}],"isi":1,"quality_controlled":"1","project":[{"_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411","name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1909.07347"],"isi":["000840292800001"]},"oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/s00454-022-00394-9","month":"04","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","year":"2023","acknowledgement":"This work was started during the 6th Austrian–Japanese–Mexican–Spanish Workshop on Discrete Geometry in June 2019 in Austria. We thank all the participants for the good atmosphere as well as discussions on the topic. Also, we thank Jan Kynčl for sending us remarks on a preliminary version of this work and an anonymous referee for further helpful comments.Alan Arroyo was funded by the Marie Skłodowska-Curie grant agreement No 754411. Fabian Klute was partially supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 612.001.651 and by the Austrian Science Fund (FWF): J-4510. Irene Parada and Birgit Vogtenhuber were partially supported by the Austrian Science Fund (FWF): W1230 and within the collaborative DACH project Arrangements and Drawings as FWF project I 3340-N35. Irene Parada was also partially supported by the Independent Research Fund Denmark grant 2020-2023 (9131-00044B) Dynamic Network Analysis and by the Margarita Salas Fellowship funded by the Ministry of Universities of Spain and the European Union (NextGenerationEU). Tilo Wiedera was supported by the German Research Foundation (DFG) grant CH 897/2-2.","date_created":"2022-08-28T22:02:01Z","date_updated":"2023-08-14T12:51:25Z","volume":69,"author":[{"last_name":"Arroyo Guevara","first_name":"Alan M","orcid":"0000-0003-2401-8670","id":"3207FDC6-F248-11E8-B48F-1D18A9856A87","full_name":"Arroyo Guevara, Alan M"},{"full_name":"Klute, Fabian","last_name":"Klute","first_name":"Fabian"},{"first_name":"Irene","last_name":"Parada","full_name":"Parada, Irene"},{"first_name":"Birgit","last_name":"Vogtenhuber","full_name":"Vogtenhuber, Birgit"},{"last_name":"Seidel","first_name":"Raimund","full_name":"Seidel, Raimund"},{"full_name":"Wiedera, Tilo","first_name":"Tilo","last_name":"Wiedera"}],"file_date_updated":"2022-08-29T11:23:15Z","ec_funded":1},{"publication_status":"published","department":[{"_id":"HeEd"}],"publisher":"Springer Nature","year":"2023","acknowledgement":"Open access funding provided by the Austrian Science Fund (FWF). This research was supported by the FWF grant, Project number I4245-N35, and by the Deutsche Forschungsgemeinschaft (DFG - German Research Foundation) - Project-ID 195170736 - TRR109.","date_created":"2023-03-26T22:01:09Z","date_updated":"2023-10-04T11:46:48Z","volume":70,"author":[{"full_name":"Kourimska, Hana","first_name":"Hana","last_name":"Kourimska","id":"D9B8E14C-3C26-11EA-98F5-1F833DDC885E","orcid":"0000-0001-7841-0091"}],"file_date_updated":"2023-10-04T11:46:24Z","isi":1,"quality_controlled":"1","project":[{"call_identifier":"FWF","name":"Algebraic Footprints of Geometric Features in Homology","_id":"26AD5D90-B435-11E9-9278-68D0E5697425","grant_number":"I04245"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"isi":["000948148000001"]},"language":[{"iso":"eng"}],"doi":"10.1007/s00454-023-00484-2","month":"07","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"status":"public","ddc":["510"],"title":"Discrete yamabe problem for polyhedral surfaces","intvolume":" 70","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12764","oa_version":"Published Version","file":[{"date_created":"2023-10-04T11:46:24Z","date_updated":"2023-10-04T11:46:24Z","checksum":"cdbf90ba4a7ddcb190d37b9e9d4cb9d3","success":1,"relation":"main_file","file_id":"14396","file_size":1026683,"content_type":"application/pdf","creator":"dernst","file_name":"2023_DiscreteGeometry_Kourimska.pdf","access_level":"open_access"}],"type":"journal_article","abstract":[{"text":"We study a new discretization of the Gaussian curvature for polyhedral surfaces. This discrete Gaussian curvature is defined on each conical singularity of a polyhedral surface as the quotient of the angle defect and the area of the Voronoi cell corresponding to the singularity. We divide polyhedral surfaces into discrete conformal classes using a generalization of discrete conformal equivalence pioneered by Feng Luo. We subsequently show that, in every discrete conformal class, there exists a polyhedral surface with constant discrete Gaussian curvature. We also provide explicit examples to demonstrate that this surface is in general not unique.","lang":"eng"}],"article_type":"original","page":"123-153","publication":"Discrete and Computational Geometry","citation":{"ama":"Kourimska H. Discrete yamabe problem for polyhedral surfaces. Discrete and Computational Geometry. 2023;70:123-153. doi:10.1007/s00454-023-00484-2","ista":"Kourimska H. 2023. Discrete yamabe problem for polyhedral surfaces. Discrete and Computational Geometry. 70, 123–153.","ieee":"H. Kourimska, “Discrete yamabe problem for polyhedral surfaces,” Discrete and Computational Geometry, vol. 70. Springer Nature, pp. 123–153, 2023.","apa":"Kourimska, H. (2023). Discrete yamabe problem for polyhedral surfaces. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00484-2","mla":"Kourimska, Hana. “Discrete Yamabe Problem for Polyhedral Surfaces.” Discrete and Computational Geometry, vol. 70, Springer Nature, 2023, pp. 123–53, doi:10.1007/s00454-023-00484-2.","short":"H. Kourimska, Discrete and Computational Geometry 70 (2023) 123–153.","chicago":"Kourimska, Hana. “Discrete Yamabe Problem for Polyhedral Surfaces.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-023-00484-2."},"date_published":"2023-07-01T00:00:00Z","scopus_import":"1","day":"01","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1"},{"doi":"10.1007/s00454-022-00476-8","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"isi":["000936496800001"],"arxiv":["2103.07823"]},"oa":1,"quality_controlled":"1","isi":1,"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"09","related_material":{"record":[{"id":"9605","status":"public","relation":"earlier_version"}]},"author":[{"full_name":"Corbet, René","first_name":"René","last_name":"Corbet"},{"full_name":"Kerber, Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","last_name":"Kerber","first_name":"Michael"},{"full_name":"Lesnick, Michael","last_name":"Lesnick","first_name":"Michael"},{"id":"464B40D6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8882-5116","first_name":"Georg F","last_name":"Osang","full_name":"Osang, Georg F"}],"volume":70,"date_updated":"2023-10-04T12:03:40Z","date_created":"2023-03-05T23:01:06Z","acknowledgement":"We thank the anonymous reviewers for many helpful comments and suggestions, which led to substantial improvements of the paper. The first two authors were supported by the Austrian Science Fund (FWF) grant number P 29984-N35 and W1230. The first author was partly supported by an Austrian Marshall Plan Scholarship, and by the Brummer & Partners MathDataLab. A conference version of this paper was presented at the 37th International Symposium on Computational Geometry (SoCG 2021). Open access funding provided by the Royal Institute of Technology.","year":"2023","department":[{"_id":"HeEd"}],"publisher":"Springer Nature","publication_status":"published","file_date_updated":"2023-03-07T14:40:14Z","date_published":"2023-09-01T00:00:00Z","citation":{"short":"R. Corbet, M. Kerber, M. Lesnick, G.F. Osang, Discrete and Computational Geometry 70 (2023) 376–405.","mla":"Corbet, René, et al. “Computing the Multicover Bifiltration.” Discrete and Computational Geometry, vol. 70, Springer Nature, 2023, pp. 376–405, doi:10.1007/s00454-022-00476-8.","chicago":"Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing the Multicover Bifiltration.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-022-00476-8.","ama":"Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration. Discrete and Computational Geometry. 2023;70:376-405. doi:10.1007/s00454-022-00476-8","ieee":"R. Corbet, M. Kerber, M. Lesnick, and G. F. Osang, “Computing the multicover bifiltration,” Discrete and Computational Geometry, vol. 70. Springer Nature, pp. 376–405, 2023.","apa":"Corbet, R., Kerber, M., Lesnick, M., & Osang, G. F. (2023). Computing the multicover bifiltration. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00476-8","ista":"Corbet R, Kerber M, Lesnick M, Osang GF. 2023. Computing the multicover bifiltration. Discrete and Computational Geometry. 70, 376–405."},"publication":"Discrete and Computational Geometry","page":"376-405","article_type":"original","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","day":"01","scopus_import":"1","oa_version":"Published Version","file":[{"content_type":"application/pdf","file_size":1359323,"creator":"cchlebak","access_level":"open_access","file_name":"2023_DisCompGeo_Corbet.pdf","checksum":"71ce7e59f7ee4620acc704fecca620c2","success":1,"date_updated":"2023-03-07T14:40:14Z","date_created":"2023-03-07T14:40:14Z","relation":"main_file","file_id":"12715"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12709","intvolume":" 70","ddc":["000"],"title":"Computing the multicover bifiltration","status":"public","abstract":[{"text":"Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.","lang":"eng"}],"type":"journal_article"},{"publication":"Discrete and Computational Geometry","citation":{"chicago":"Fulek, Radoslav, Bernd Gärtner, Andrey Kupavskii, Pavel Valtr, and Uli Wagner. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-023-00532-x.","short":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, U. Wagner, Discrete and Computational Geometry (2023).","mla":"Fulek, Radoslav, et al. “The Crossing Tverberg Theorem.” Discrete and Computational Geometry, Springer Nature, 2023, doi:10.1007/s00454-023-00532-x.","apa":"Fulek, R., Gärtner, B., Kupavskii, A., Valtr, P., & Wagner, U. (2023). The crossing Tverberg theorem. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00532-x","ieee":"R. Fulek, B. Gärtner, A. Kupavskii, P. Valtr, and U. Wagner, “The crossing Tverberg theorem,” Discrete and Computational Geometry. Springer Nature, 2023.","ista":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. 2023. The crossing Tverberg theorem. Discrete and Computational Geometry.","ama":"Fulek R, Gärtner B, Kupavskii A, Valtr P, Wagner U. The crossing Tverberg theorem. Discrete and Computational Geometry. 2023. doi:10.1007/s00454-023-00532-x"},"article_type":"original","date_published":"2023-07-27T00:00:00Z","scopus_import":"1","day":"27","article_processing_charge":"No","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"13974","status":"public","title":"The crossing Tverberg theorem","oa_version":"Preprint","type":"journal_article","abstract":[{"text":"The Tverberg theorem is one of the cornerstones of discrete geometry. It states that, given a set X of at least (d+1)(r−1)+1 points in Rd, one can find a partition X=X1∪⋯∪Xr of X, such that the convex hulls of the Xi, i=1,…,r, all share a common point. In this paper, we prove a trengthening of this theorem that guarantees a partition which, in addition to the above, has the property that the boundaries of full-dimensional convex hulls have pairwise nonempty intersections. Possible generalizations and algorithmic aspects are also discussed. As a concrete application, we show that any n points in the plane in general position span ⌊n/3⌋ vertex-disjoint triangles that are pairwise crossing, meaning that their boundaries have pairwise nonempty intersections; this number is clearly best possible. A previous result of Álvarez-Rebollar et al. guarantees ⌊n/6⌋pairwise crossing triangles. Our result generalizes to a result about simplices in Rd, d≥2.","lang":"eng"}],"external_id":{"arxiv":["1812.04911"],"isi":["001038546500001"]},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1812.04911","open_access":"1"}],"oa":1,"isi":1,"quality_controlled":"1","project":[{"call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","_id":"261FA626-B435-11E9-9278-68D0E5697425","grant_number":"M02281"}],"doi":"10.1007/s00454-023-00532-x","language":[{"iso":"eng"}],"month":"07","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"year":"2023","acknowledgement":"Part of the research leading to this paper was done during the 16th Gremo Workshop on Open Problems (GWOP), Waltensburg, Switzerland, June 12–16, 2018. We thank Patrick Schnider for suggesting the problem, and Stefan Felsner, Malte Milatz, and Emo Welzl for fruitful discussions during the workshop. We also thank Stefan Felsner and Manfred Scheucher for finding, communicating the example from Sect. 3.3, and the kind permission to include their visualization of the point set. We thank Dömötör Pálvölgyi, the SoCG reviewers, and DCG reviewers for various helpful comments.\r\nR. Fulek gratefully acknowledges support from Austrian Science Fund (FWF), Project M2281-N35. A. Kupavskii was supported by the Advanced Postdoc.Mobility Grant no. P300P2_177839 of the Swiss National Science Foundation. Research by P. Valtr was supported by the Grant no. 18-19158 S of the Czech Science Foundation (GAČR).","publication_status":"epub_ahead","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","author":[{"full_name":"Fulek, Radoslav","orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav"},{"last_name":"Gärtner","first_name":"Bernd","full_name":"Gärtner, Bernd"},{"last_name":"Kupavskii","first_name":"Andrey","full_name":"Kupavskii, Andrey"},{"full_name":"Valtr, Pavel","first_name":"Pavel","last_name":"Valtr"},{"orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli","full_name":"Wagner, Uli"}],"related_material":{"record":[{"id":"6647","relation":"earlier_version","status":"public"}]},"date_updated":"2023-12-13T12:03:35Z","date_created":"2023-08-06T22:01:12Z"},{"article_type":"original","citation":{"short":"H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, M. Saghafian, Discrete and Computational Geometry (2023).","mla":"Edelsbrunner, Herbert, et al. “On Angles in Higher Order Brillouin Tessellations and Related Tilings in the Plane.” Discrete and Computational Geometry, Springer Nature, 2023, doi:10.1007/s00454-023-00566-1.","chicago":"Edelsbrunner, Herbert, Alexey Garber, Mohadese Ghafari, Teresa Heiss, and Morteza Saghafian. “On Angles in Higher Order Brillouin Tessellations and Related Tilings in the Plane.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-023-00566-1.","ama":"Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. On angles in higher order Brillouin tessellations and related tilings in the plane. Discrete and Computational Geometry. 2023. doi:10.1007/s00454-023-00566-1","apa":"Edelsbrunner, H., Garber, A., Ghafari, M., Heiss, T., & Saghafian, M. (2023). On angles in higher order Brillouin tessellations and related tilings in the plane. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00566-1","ieee":"H. Edelsbrunner, A. Garber, M. Ghafari, T. Heiss, and M. Saghafian, “On angles in higher order Brillouin tessellations and related tilings in the plane,” Discrete and Computational Geometry. Springer Nature, 2023.","ista":"Edelsbrunner H, Garber A, Ghafari M, Heiss T, Saghafian M. 2023. On angles in higher order Brillouin tessellations and related tilings in the plane. Discrete and Computational Geometry."},"publication":"Discrete and Computational Geometry","date_published":"2023-09-07T00:00:00Z","scopus_import":"1","article_processing_charge":"Yes (via OA deal)","day":"07","title":"On angles in higher order Brillouin tessellations and related tilings in the plane","status":"public","_id":"14345","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","oa_version":"Published Version","type":"journal_article","abstract":[{"lang":"eng","text":"For a locally finite set in R2, the order-k Brillouin tessellations form an infinite sequence of convex face-to-face tilings of the plane. If the set is coarsely dense and generic, then the corresponding infinite sequences of minimum and maximum angles are both monotonic in k. As an example, a stationary Poisson point process in R2 is locally finite, coarsely dense, and generic with probability one. For such a set, the distributions of angles in the Voronoi tessellations, Delaunay mosaics, and Brillouin tessellations are independent of the order and can be derived from the formula for angles in order-1 Delaunay mosaics given by Miles (Math. Biosci. 6, 85–127 (1970))."}],"project":[{"name":"Alpha Shape Theory Extended","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183"},{"_id":"268116B8-B435-11E9-9278-68D0E5697425","grant_number":"Z00342","name":"The Wittgenstein Prize","call_identifier":"FWF"},{"call_identifier":"FWF","name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35"}],"quality_controlled":"1","isi":1,"external_id":{"isi":["001060727600004"],"arxiv":["2204.01076"]},"oa":1,"main_file_link":[{"url":"https://doi.org/10.1007/s00454-023-00566-1","open_access":"1"}],"language":[{"iso":"eng"}],"doi":"10.1007/s00454-023-00566-1","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"09","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"publication_status":"epub_ahead","acknowledgement":"Work by all authors but A. Garber is supported by the European Research Council (ERC), Grant No. 788183, by the Wittgenstein Prize, Austrian Science Fund (FWF), Grant No. Z 342-N31, and by the DFG Collaborative Research Center TRR 109, Austrian Science Fund (FWF), Grant No. I 02979-N35. Work by A. Garber is partially supported by the Alexander von Humboldt Foundation.","year":"2023","date_updated":"2023-12-13T12:25:06Z","date_created":"2023-09-17T22:01:10Z","author":[{"first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"full_name":"Garber, Alexey","first_name":"Alexey","last_name":"Garber"},{"first_name":"Mohadese","last_name":"Ghafari","full_name":"Ghafari, Mohadese"},{"full_name":"Heiss, Teresa","first_name":"Teresa","last_name":"Heiss","id":"4879BB4E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1780-2689"},{"full_name":"Saghafian, Morteza","id":"f86f7148-b140-11ec-9577-95435b8df824","first_name":"Morteza","last_name":"Saghafian"}],"ec_funded":1},{"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"month":"07","language":[{"iso":"eng"}],"doi":"10.1007/s00454-023-00500-5","quality_controlled":"1","isi":1,"external_id":{"arxiv":["2107.04112"],"isi":["001023742800003"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"file_date_updated":"2024-01-29T11:15:22Z","volume":70,"date_created":"2023-07-23T22:01:14Z","date_updated":"2024-01-29T11:16:16Z","author":[{"last_name":"Brunck","first_name":"Florestan R","id":"6ab6e556-f394-11eb-9cf6-9dfb78f00d8d","full_name":"Brunck, Florestan R"}],"department":[{"_id":"UlWa"}],"publisher":"Springer Nature","publication_status":"published","year":"2023","acknowledgement":"Open access funding provided by the Institute of Science and Technology (IST Austria).","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","day":"05","scopus_import":"1","date_published":"2023-07-05T00:00:00Z","page":"1059-1089","article_type":"original","citation":{"ama":"Brunck FR. Iterated medial triangle subdivision in surfaces of constant curvature. Discrete and Computational Geometry. 2023;70(3):1059-1089. doi:10.1007/s00454-023-00500-5","ista":"Brunck FR. 2023. Iterated medial triangle subdivision in surfaces of constant curvature. Discrete and Computational Geometry. 70(3), 1059–1089.","apa":"Brunck, F. R. (2023). Iterated medial triangle subdivision in surfaces of constant curvature. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-023-00500-5","ieee":"F. R. Brunck, “Iterated medial triangle subdivision in surfaces of constant curvature,” Discrete and Computational Geometry, vol. 70, no. 3. Springer Nature, pp. 1059–1089, 2023.","mla":"Brunck, Florestan R. “Iterated Medial Triangle Subdivision in Surfaces of Constant Curvature.” Discrete and Computational Geometry, vol. 70, no. 3, Springer Nature, 2023, pp. 1059–89, doi:10.1007/s00454-023-00500-5.","short":"F.R. Brunck, Discrete and Computational Geometry 70 (2023) 1059–1089.","chicago":"Brunck, Florestan R. “Iterated Medial Triangle Subdivision in Surfaces of Constant Curvature.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-023-00500-5."},"publication":"Discrete and Computational Geometry","issue":"3","abstract":[{"lang":"eng","text":"Consider a geodesic triangle on a surface of constant curvature and subdivide it recursively into four triangles by joining the midpoints of its edges. We show the existence of a uniform δ>0\r\n such that, at any step of the subdivision, all the triangle angles lie in the interval (δ,π−δ)\r\n. Additionally, we exhibit stabilising behaviours for both angles and lengths as this subdivision progresses."}],"type":"journal_article","oa_version":"Published Version","file":[{"file_size":1466020,"content_type":"application/pdf","creator":"dernst","file_name":"2023_DiscreteComputGeometry_Brunck.pdf","access_level":"open_access","date_updated":"2024-01-29T11:15:22Z","date_created":"2024-01-29T11:15:22Z","checksum":"865e68daafdd4edcfc280172ec50f5ea","success":1,"relation":"main_file","file_id":"14897"}],"intvolume":" 70","status":"public","title":"Iterated medial triangle subdivision in surfaces of constant curvature","ddc":["510"],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"13270"},{"day":"01","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","scopus_import":"1","date_published":"2022-04-01T00:00:00Z","publication":"Discrete and Computational Geometry","citation":{"mla":"Biswas, Ranita, et al. “Continuous and Discrete Radius Functions on Voronoi Tessellations and Delaunay Mosaics.” Discrete and Computational Geometry, vol. 67, Springer Nature, 2022, pp. 811–42, doi:10.1007/s00454-022-00371-2.","short":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, M. Saghafian, Discrete and Computational Geometry 67 (2022) 811–842.","chicago":"Biswas, Ranita, Sebastiano Cultrera di Montesano, Herbert Edelsbrunner, and Morteza Saghafian. “Continuous and Discrete Radius Functions on Voronoi Tessellations and Delaunay Mosaics.” Discrete and Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-022-00371-2.","ama":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. Continuous and discrete radius functions on Voronoi tessellations and Delaunay mosaics. Discrete and Computational Geometry. 2022;67:811-842. doi:10.1007/s00454-022-00371-2","ista":"Biswas R, Cultrera di Montesano S, Edelsbrunner H, Saghafian M. 2022. Continuous and discrete radius functions on Voronoi tessellations and Delaunay mosaics. Discrete and Computational Geometry. 67, 811–842.","apa":"Biswas, R., Cultrera di Montesano, S., Edelsbrunner, H., & Saghafian, M. (2022). Continuous and discrete radius functions on Voronoi tessellations and Delaunay mosaics. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00371-2","ieee":"R. Biswas, S. Cultrera di Montesano, H. Edelsbrunner, and M. Saghafian, “Continuous and discrete radius functions on Voronoi tessellations and Delaunay mosaics,” Discrete and Computational Geometry, vol. 67. Springer Nature, pp. 811–842, 2022."},"article_type":"original","page":"811-842","abstract":[{"lang":"eng","text":"The Voronoi tessellation in Rd is defined by locally minimizing the power distance to given weighted points. Symmetrically, the Delaunay mosaic can be defined by locally maximizing the negative power distance to other such points. We prove that the average of the two piecewise quadratic functions is piecewise linear, and that all three functions have the same critical points and values. Discretizing the two piecewise quadratic functions, we get the alpha shapes as sublevel sets of the discrete function on the Delaunay mosaic, and analogous shapes as superlevel sets of the discrete function on the Voronoi tessellation. For the same non-critical value, the corresponding shapes are disjoint, separated by a narrow channel that contains no critical points but the entire level set of the piecewise linear function."}],"type":"journal_article","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"2022_DiscreteCompGeometry_Biswas.pdf","content_type":"application/pdf","file_size":2518111,"creator":"dernst","relation":"main_file","file_id":"11718","checksum":"9383d3b70561bacee905e335dc922680","success":1,"date_created":"2022-08-02T06:07:55Z","date_updated":"2022-08-02T06:07:55Z"}],"_id":"10773","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","status":"public","title":"Continuous and discrete radius functions on Voronoi tessellations and Delaunay mosaics","ddc":["510"],"intvolume":" 67","month":"04","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"doi":"10.1007/s00454-022-00371-2","language":[{"iso":"eng"}],"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"isi":["000752175300002"]},"quality_controlled":"1","isi":1,"file_date_updated":"2022-08-02T06:07:55Z","author":[{"first_name":"Ranita","last_name":"Biswas","id":"3C2B033E-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-5372-7890","full_name":"Biswas, Ranita"},{"full_name":"Cultrera Di Montesano, Sebastiano","orcid":"0000-0001-6249-0832","id":"34D2A09C-F248-11E8-B48F-1D18A9856A87","last_name":"Cultrera Di Montesano","first_name":"Sebastiano"},{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"last_name":"Saghafian","first_name":"Morteza","full_name":"Saghafian, Morteza"}],"date_updated":"2023-08-02T14:31:25Z","date_created":"2022-02-20T23:01:34Z","volume":67,"year":"2022","acknowledgement":"Open access funding provided by the Institute of Science and Technology (IST Austria).","publication_status":"published","publisher":"Springer Nature","department":[{"_id":"HeEd"}]},{"month":"12","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"doi":"10.1007/s00454-021-00364-7","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/2003.13536"}],"external_id":{"isi":["000750681500001"],"arxiv":["2003.13536"]},"oa":1,"isi":1,"quality_controlled":"1","author":[{"full_name":"Patakova, Zuzana","first_name":"Zuzana","last_name":"Patakova","id":"48B57058-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-3975-1683"},{"full_name":"Tancer, Martin","last_name":"Tancer","first_name":"Martin"},{"full_name":"Wagner, Uli","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner"}],"date_created":"2022-02-20T23:01:35Z","date_updated":"2023-08-02T14:38:58Z","volume":68,"acknowledgement":"The work by Zuzana Patáková has been partially supported by Charles University Research Center Program No. UNCE/SCI/022, and part of it was done during her research stay at IST Austria. The work by Martin Tancer is supported by the GAČR Grant 19-04113Y and by the Charles University Projects PRIMUS/17/SCI/3 and UNCE/SCI/004.","year":"2022","publication_status":"published","publisher":"Springer Nature","department":[{"_id":"UlWa"}],"day":"01","article_processing_charge":"No","scopus_import":"1","date_published":"2022-12-01T00:00:00Z","publication":"Discrete and Computational Geometry","citation":{"ama":"Patakova Z, Tancer M, Wagner U. Barycentric cuts through a convex body. Discrete and Computational Geometry. 2022;68:1133-1154. doi:10.1007/s00454-021-00364-7","ista":"Patakova Z, Tancer M, Wagner U. 2022. Barycentric cuts through a convex body. Discrete and Computational Geometry. 68, 1133–1154.","ieee":"Z. Patakova, M. Tancer, and U. Wagner, “Barycentric cuts through a convex body,” Discrete and Computational Geometry, vol. 68. Springer Nature, pp. 1133–1154, 2022.","apa":"Patakova, Z., Tancer, M., & Wagner, U. (2022). Barycentric cuts through a convex body. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-021-00364-7","mla":"Patakova, Zuzana, et al. “Barycentric Cuts through a Convex Body.” Discrete and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 1133–54, doi:10.1007/s00454-021-00364-7.","short":"Z. Patakova, M. Tancer, U. Wagner, Discrete and Computational Geometry 68 (2022) 1133–1154.","chicago":"Patakova, Zuzana, Martin Tancer, and Uli Wagner. “Barycentric Cuts through a Convex Body.” Discrete and Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-021-00364-7."},"article_type":"original","page":"1133-1154","abstract":[{"lang":"eng","text":"Let K be a convex body in Rn (i.e., a compact convex set with nonempty interior). Given a point p in the interior of K, a hyperplane h passing through p is called barycentric if p is the barycenter of K∩h. In 1961, Grünbaum raised the question whether, for every K, there exists an interior point p through which there are at least n+1 distinct barycentric hyperplanes. Two years later, this was seemingly resolved affirmatively by showing that this is the case if p=p0 is the point of maximal depth in K. However, while working on a related question, we noticed that one of the auxiliary claims in the proof is incorrect. Here, we provide a counterexample; this re-opens Grünbaum’s question. It follows from known results that for n≥2, there are always at least three distinct barycentric cuts through the point p0∈K of maximal depth. Using tools related to Morse theory we are able to improve this bound: four distinct barycentric cuts through p0 are guaranteed if n≥3."}],"type":"journal_article","oa_version":"Preprint","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"10776","status":"public","title":"Barycentric cuts through a convex body","intvolume":" 68"},{"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"isi":["000883222200003"]},"isi":1,"quality_controlled":"1","doi":"10.1007/s00454-022-00436-2","language":[{"iso":"eng"}],"month":"11","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"year":"2022","acknowledgement":"This is a full and revised version of [38] (on partial triangulations) in Proceedings of the 36th Annual International Symposium on Computational Geometry (SoCG‘20) and of some of the results in [37] (on full triangulations) in Proceedings of the 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA‘20).\r\nThis research started at the 11th Gremo’s Workshop on Open Problems (GWOP), Alp Sellamatt, Switzerland, June 24–28, 2013, motivated by a question posed by Filip Mori´c on full triangulations. Research was supported by the Swiss National Science Foundation within the collaborative DACH project Arrangements and Drawings as SNSF Project 200021E-171681, and by IST Austria and Berlin Free University during a sabbatical stay of the second author. We thank Michael Joswig, Jesús De Loera, and Francisco Santos for helpful discussions on the topics of this paper, and Daniel Bertschinger and Valentin Stoppiello for carefully reading earlier versions and for many helpful comments.\r\nOpen access funding provided by the Swiss Federal Institute of Technology Zürich","publication_status":"published","department":[{"_id":"UlWa"}],"publisher":"Springer Nature","author":[{"first_name":"Uli","last_name":"Wagner","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","full_name":"Wagner, Uli"},{"last_name":"Welzl","first_name":"Emo","full_name":"Welzl, Emo"}],"related_material":{"record":[{"id":"7807","status":"public","relation":"earlier_version"},{"id":"7990","relation":"earlier_version","status":"public"}]},"date_created":"2023-01-12T12:02:28Z","date_updated":"2023-08-04T08:51:08Z","volume":68,"file_date_updated":"2023-01-23T11:10:03Z","publication":"Discrete & Computational Geometry","citation":{"ama":"Wagner U, Welzl E. Connectivity of triangulation flip graphs in the plane. Discrete & Computational Geometry. 2022;68(4):1227-1284. doi:10.1007/s00454-022-00436-2","apa":"Wagner, U., & Welzl, E. (2022). Connectivity of triangulation flip graphs in the plane. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00436-2","ieee":"U. Wagner and E. Welzl, “Connectivity of triangulation flip graphs in the plane,” Discrete & Computational Geometry, vol. 68, no. 4. Springer Nature, pp. 1227–1284, 2022.","ista":"Wagner U, Welzl E. 2022. Connectivity of triangulation flip graphs in the plane. Discrete & Computational Geometry. 68(4), 1227–1284.","short":"U. Wagner, E. Welzl, Discrete & Computational Geometry 68 (2022) 1227–1284.","mla":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” Discrete & Computational Geometry, vol. 68, no. 4, Springer Nature, 2022, pp. 1227–84, doi:10.1007/s00454-022-00436-2.","chicago":"Wagner, Uli, and Emo Welzl. “Connectivity of Triangulation Flip Graphs in the Plane.” Discrete & Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-022-00436-2."},"article_type":"original","page":"1227-1284","date_published":"2022-11-14T00:00:00Z","scopus_import":"1","keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"day":"14","has_accepted_license":"1","article_processing_charge":"No","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","_id":"12129","status":"public","ddc":["510"],"title":"Connectivity of triangulation flip graphs in the plane","intvolume":" 68","file":[{"relation":"main_file","file_id":"12345","checksum":"307e879d09e52eddf5b225d0aaa9213a","success":1,"date_updated":"2023-01-23T11:10:03Z","date_created":"2023-01-23T11:10:03Z","access_level":"open_access","file_name":"2022_DiscreteCompGeometry_Wagner.pdf","content_type":"application/pdf","file_size":1747581,"creator":"dernst"}],"oa_version":"Published Version","type":"journal_article","abstract":[{"text":"Given a finite point set P in general position in the plane, a full triangulation of P is a maximal straight-line embedded plane graph on P. A partial triangulation of P is a full triangulation of some subset P′ of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge (called edge flip), removes a non-extreme point of degree 3, or adds a point in P∖P′ as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The edge flip graph is defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For sets P of n points in the plane in general position, we show that the edge flip graph is ⌈n/2−2⌉-vertex connected, and the bistellar flip graph is (n−3)-vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where (n−3)-vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski’s Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided that n is large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension ⌈n/2−2⌉ (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension n−3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n−3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height n−3. (iv) There are arbitrarily large sets P with non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations.","lang":"eng"}],"issue":"4"},{"language":[{"iso":"eng"}],"doi":"10.1007/s00454-022-00412-w","project":[{"call_identifier":"FWF","name":"Eliminating intersections in drawings of graphs","grant_number":"M02281","_id":"261FA626-B435-11E9-9278-68D0E5697425"}],"isi":1,"quality_controlled":"1","main_file_link":[{"open_access":"1","url":"https://arxiv.org/abs/1803.05085"}],"oa":1,"external_id":{"isi":["000825014500001"],"arxiv":["1803.05085"]},"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"09","volume":68,"date_created":"2022-07-17T22:01:56Z","date_updated":"2023-08-14T12:43:52Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"186"}]},"author":[{"orcid":"0000-0001-8485-1774","id":"39F3FFE4-F248-11E8-B48F-1D18A9856A87","last_name":"Fulek","first_name":"Radoslav","full_name":"Fulek, Radoslav"},{"full_name":"Kynčl, Jan","first_name":"Jan","last_name":"Kynčl"}],"department":[{"_id":"UlWa"}],"publisher":"Springer Nature","publication_status":"published","year":"2022","acknowledgement":"We thank Zdeněk Dvořák, Xavier Goaoc, and Pavel Paták for helpful discussions. We also thank Bojan Mohar, Paul Seymour, Gelasio Salazar, Jim Geelen, and John Maharry for information about their unpublished results related to Conjecture 3.1. Finally we thank the reviewers for corrections and suggestions for improving the presentation.\r\nSupported by Austrian Science Fund (FWF): M2281-N35. Supported by project 19-04113Y of the Czech Science Foundation (GAČR), by the Czech-French collaboration project EMBEDS II (CZ: 7AMB17FR029, FR: 38087RM), and by Charles University project UNCE/SCI/004.","date_published":"2022-09-01T00:00:00Z","page":"425-447","article_type":"original","citation":{"ama":"Fulek R, Kynčl J. The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. 2022;68:425-447. doi:10.1007/s00454-022-00412-w","ista":"Fulek R, Kynčl J. 2022. The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. 68, 425–447.","apa":"Fulek, R., & Kynčl, J. (2022). The Z2-Genus of Kuratowski minors. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00412-w","ieee":"R. Fulek and J. Kynčl, “The Z2-Genus of Kuratowski minors,” Discrete and Computational Geometry, vol. 68. Springer Nature, pp. 425–447, 2022.","mla":"Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” Discrete and Computational Geometry, vol. 68, Springer Nature, 2022, pp. 425–47, doi:10.1007/s00454-022-00412-w.","short":"R. Fulek, J. Kynčl, Discrete and Computational Geometry 68 (2022) 425–447.","chicago":"Fulek, Radoslav, and Jan Kynčl. “The Z2-Genus of Kuratowski Minors.” Discrete and Computational Geometry. Springer Nature, 2022. https://doi.org/10.1007/s00454-022-00412-w."},"publication":"Discrete and Computational Geometry","article_processing_charge":"No","day":"01","scopus_import":"1","oa_version":"Preprint","intvolume":" 68","title":"The Z2-Genus of Kuratowski minors","status":"public","_id":"11593","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","abstract":[{"text":"A drawing of a graph on a surface is independently even if every pair of nonadjacent edges in the drawing crosses an even number of times. The Z2 -genus of a graph G is the minimum g such that G has an independently even drawing on the orientable surface of genus g. An unpublished result by Robertson and Seymour implies that for every t, every graph of sufficiently large genus contains as a minor a projective t×t grid or one of the following so-called t -Kuratowski graphs: K3,t, or t copies of K5 or K3,3 sharing at most two common vertices. We show that the Z2-genus of graphs in these families is unbounded in t; in fact, equal to their genus. Together, this implies that the genus of a graph is bounded from above by a function of its Z2-genus, solving a problem posed by Schaefer and Štefankovič, and giving an approximate version of the Hanani–Tutte theorem on orientable surfaces. We also obtain an analogous result for Euler genus and Euler Z2-genus of graphs.","lang":"eng"}],"type":"journal_article"},{"language":[{"iso":"eng"}],"doi":"10.1007/s00454-021-00299-z","quality_controlled":"1","external_id":{"arxiv":["1910.12628"]},"month":"10","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"date_created":"2022-06-17T08:45:15Z","date_updated":"2023-02-23T13:26:41Z","volume":66,"author":[{"id":"3827DAC8-F248-11E8-B48F-1D18A9856A87","first_name":"Sergey","last_name":"Avvakumov","full_name":"Avvakumov, Sergey"},{"last_name":"Kudrya","first_name":"Sergey","id":"ecf01965-d252-11ea-95a5-8ada5f6c6a67","full_name":"Kudrya, Sergey"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"8182"}]},"publication_status":"published","publisher":"Springer Nature","year":"2021","acknowledgement":"S. Avvakumov has received funding from the European Research Council under the European Union’s Seventh Framework Programme ERC Grant agreement ERC StG 716424–CASe. S. Kudrya was supported by the Austrian Academic Exchange Service (OeAD), ICM-2019-13577.","extern":"1","date_published":"2021-10-01T00:00:00Z","article_type":"original","page":"1202-1216","publication":"Discrete & Computational Geometry","citation":{"chicago":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” Discrete & Computational Geometry. Springer Nature, 2021. https://doi.org/10.1007/s00454-021-00299-z.","mla":"Avvakumov, Sergey, and Sergey Kudrya. “Vanishing of All Equivariant Obstructions and the Mapping Degree.” Discrete & Computational Geometry, vol. 66, no. 3, Springer Nature, 2021, pp. 1202–16, doi:10.1007/s00454-021-00299-z.","short":"S. Avvakumov, S. Kudrya, Discrete & Computational Geometry 66 (2021) 1202–1216.","ista":"Avvakumov S, Kudrya S. 2021. Vanishing of all equivariant obstructions and the mapping degree. Discrete & Computational Geometry. 66(3), 1202–1216.","apa":"Avvakumov, S., & Kudrya, S. (2021). Vanishing of all equivariant obstructions and the mapping degree. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-021-00299-z","ieee":"S. Avvakumov and S. Kudrya, “Vanishing of all equivariant obstructions and the mapping degree,” Discrete & Computational Geometry, vol. 66, no. 3. Springer Nature, pp. 1202–1216, 2021.","ama":"Avvakumov S, Kudrya S. Vanishing of all equivariant obstructions and the mapping degree. Discrete & Computational Geometry. 2021;66(3):1202-1216. doi:10.1007/s00454-021-00299-z"},"day":"01","article_processing_charge":"No","keyword":["Computational Theory and Mathematics","Discrete Mathematics and Combinatorics","Geometry and Topology","Theoretical Computer Science"],"scopus_import":"1","oa_version":"Preprint","title":"Vanishing of all equivariant obstructions and the mapping degree","status":"public","intvolume":" 66","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"11446","abstract":[{"lang":"eng","text":"Suppose that n is not a prime power and not twice a prime power. We prove that for any Hausdorff compactum X with a free action of the symmetric group Sn, there exists an Sn-equivariant map X→Rn whose image avoids the diagonal {(x,x,…,x)∈Rn∣x∈R}. Previously, the special cases of this statement for certain X were usually proved using the equivartiant obstruction theory. Such calculations are difficult and may become infeasible past the first (primary) obstruction. We take a different approach which allows us to prove the vanishing of all obstructions simultaneously. The essential step in the proof is classifying the possible degrees of Sn-equivariant maps from the boundary ∂Δn−1 of (n−1)-simplex to itself. Existence of equivariant maps between spaces is important for many questions arising from discrete mathematics and geometry, such as Kneser’s conjecture, the Square Peg conjecture, the Splitting Necklace problem, and the Topological Tverberg conjecture, etc. We demonstrate the utility of our result applying it to one such question, a specific instance of envy-free division problem."}],"issue":"3","type":"journal_article"},{"ec_funded":1,"file_date_updated":"2021-12-01T10:56:53Z","volume":65,"date_created":"2021-04-11T22:01:15Z","date_updated":"2023-08-07T14:35:44Z","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"187"}]},"author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"id":"464B40D6-F248-11E8-B48F-1D18A9856A87","last_name":"Osang","first_name":"Georg F","full_name":"Osang, Georg F"}],"department":[{"_id":"HeEd"}],"publisher":"Springer Nature","publication_status":"published","year":"2021","acknowledgement":"This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 78818 Alpha), and by the DFG Collaborative Research Center TRR 109, ‘Discretization in Geometry and Dynamics’, through Grant No. I02979-N35 of the Austrian Science Fund (FWF)\r\nOpen Access funding provided by the Institute of Science and Technology (IST Austria).","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"03","language":[{"iso":"eng"}],"doi":"10.1007/s00454-021-00281-9","project":[{"call_identifier":"H2020","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183"},{"_id":"2561EBF4-B435-11E9-9278-68D0E5697425","grant_number":"I02979-N35","call_identifier":"FWF","name":"Persistence and stability of geometric complexes"}],"quality_controlled":"1","isi":1,"oa":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"isi":["000635460400001"]},"abstract":[{"lang":"eng","text":"Given a locally finite X⊆Rd and a radius r≥0, the k-fold cover of X and r consists of all points in Rd that have k or more points of X within distance r. We consider two filtrations—one in scale obtained by fixing k and increasing r, and the other in depth obtained by fixing r and decreasing k—and we compute the persistence diagrams of both. While standard methods suffice for the filtration in scale, we need novel geometric and topological concepts for the filtration in depth. In particular, we introduce a rhomboid tiling in Rd+1 whose horizontal integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module of Delaunay mosaics that is isomorphic to the persistence module of the multi-covers."}],"type":"journal_article","oa_version":"Published Version","file":[{"access_level":"open_access","file_name":"2021_DisCompGeo_Edelsbrunner_Osang.pdf","content_type":"application/pdf","file_size":677704,"creator":"cchlebak","relation":"main_file","file_id":"10394","checksum":"59b4e1e827e494209bcb4aae22e1d347","success":1,"date_updated":"2021-12-01T10:56:53Z","date_created":"2021-12-01T10:56:53Z"}],"intvolume":" 65","status":"public","ddc":["516"],"title":"The multi-cover persistence of Euclidean balls","_id":"9317","user_id":"4359f0d1-fa6c-11eb-b949-802e58b17ae8","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","day":"31","scopus_import":"1","date_published":"2021-03-31T00:00:00Z","page":"1296–1313","article_type":"original","citation":{"short":"H. Edelsbrunner, G.F. Osang, Discrete and Computational Geometry 65 (2021) 1296–1313.","mla":"Edelsbrunner, Herbert, and Georg F. Osang. “The Multi-Cover Persistence of Euclidean Balls.” Discrete and Computational Geometry, vol. 65, Springer Nature, 2021, pp. 1296–1313, doi:10.1007/s00454-021-00281-9.","chicago":"Edelsbrunner, Herbert, and Georg F Osang. “The Multi-Cover Persistence of Euclidean Balls.” Discrete and Computational Geometry. Springer Nature, 2021. https://doi.org/10.1007/s00454-021-00281-9.","ama":"Edelsbrunner H, Osang GF. The multi-cover persistence of Euclidean balls. Discrete and Computational Geometry. 2021;65:1296–1313. doi:10.1007/s00454-021-00281-9","apa":"Edelsbrunner, H., & Osang, G. F. (2021). The multi-cover persistence of Euclidean balls. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-021-00281-9","ieee":"H. Edelsbrunner and G. F. Osang, “The multi-cover persistence of Euclidean balls,” Discrete and Computational Geometry, vol. 65. Springer Nature, pp. 1296–1313, 2021.","ista":"Edelsbrunner H, Osang GF. 2021. The multi-cover persistence of Euclidean balls. Discrete and Computational Geometry. 65, 1296–1313."},"publication":"Discrete and Computational Geometry"},{"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"07","doi":"10.1007/s00454-020-00250-8","language":[{"iso":"eng"}],"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"external_id":{"isi":["000597770300001"]},"project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","grant_number":"754411","_id":"260C2330-B435-11E9-9278-68D0E5697425"}],"quality_controlled":"1","isi":1,"ec_funded":1,"file_date_updated":"2021-08-06T09:52:29Z","author":[{"full_name":"Boissonnat, Jean-Daniel","first_name":"Jean-Daniel","last_name":"Boissonnat"},{"first_name":"Siargey","last_name":"Kachanovich","full_name":"Kachanovich, Siargey"},{"full_name":"Wintraecken, Mathijs","orcid":"0000-0002-7472-2220","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","last_name":"Wintraecken","first_name":"Mathijs"}],"volume":66,"date_created":"2020-12-12T11:07:02Z","date_updated":"2023-09-05T15:02:40Z","year":"2021","acknowledgement":"This work has been funded by the European Research Council under the European Union’s ERC Grant Agreement Number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). The third author also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411. Open access funding provided by the Institute of Science and Technology (IST Austria).","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"publication_status":"published","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","day":"01","keyword":["Theoretical Computer Science","Computational Theory and Mathematics","Geometry and Topology","Discrete Mathematics and Combinatorics"],"date_published":"2021-07-01T00:00:00Z","citation":{"ieee":"J.-D. Boissonnat, S. Kachanovich, and M. Wintraecken, “Triangulating submanifolds: An elementary and quantified version of Whitney’s method,” Discrete & Computational Geometry, vol. 66, no. 1. Springer Nature, pp. 386–434, 2021.","apa":"Boissonnat, J.-D., Kachanovich, S., & Wintraecken, M. (2021). Triangulating submanifolds: An elementary and quantified version of Whitney’s method. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00250-8","ista":"Boissonnat J-D, Kachanovich S, Wintraecken M. 2021. Triangulating submanifolds: An elementary and quantified version of Whitney’s method. Discrete & Computational Geometry. 66(1), 386–434.","ama":"Boissonnat J-D, Kachanovich S, Wintraecken M. Triangulating submanifolds: An elementary and quantified version of Whitney’s method. Discrete & Computational Geometry. 2021;66(1):386-434. doi:10.1007/s00454-020-00250-8","chicago":"Boissonnat, Jean-Daniel, Siargey Kachanovich, and Mathijs Wintraecken. “Triangulating Submanifolds: An Elementary and Quantified Version of Whitney’s Method.” Discrete & Computational Geometry. Springer Nature, 2021. https://doi.org/10.1007/s00454-020-00250-8.","short":"J.-D. Boissonnat, S. Kachanovich, M. Wintraecken, Discrete & Computational Geometry 66 (2021) 386–434.","mla":"Boissonnat, Jean-Daniel, et al. “Triangulating Submanifolds: An Elementary and Quantified Version of Whitney’s Method.” Discrete & Computational Geometry, vol. 66, no. 1, Springer Nature, 2021, pp. 386–434, doi:10.1007/s00454-020-00250-8."},"publication":"Discrete & Computational Geometry","page":"386-434","article_type":"original","issue":"1","abstract":[{"text":"We quantise Whitney’s construction to prove the existence of a triangulation for any C^2 manifold, so that we get an algorithm with explicit bounds. We also give a new elementary proof, which is completely geometric.","lang":"eng"}],"type":"journal_article","oa_version":"Published Version","file":[{"creator":"kschuh","file_size":983307,"content_type":"application/pdf","file_name":"2021_DescreteCompGeopmetry_Boissonnat.pdf","access_level":"open_access","date_updated":"2021-08-06T09:52:29Z","date_created":"2021-08-06T09:52:29Z","success":1,"checksum":"c848986091e56699dc12de85adb1e39c","file_id":"9795","relation":"main_file"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","_id":"8940","intvolume":" 66","status":"public","ddc":["516"],"title":"Triangulating submanifolds: An elementary and quantified version of Whitney’s method"},{"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"month":"10","language":[{"iso":"eng"}],"doi":"10.1007/s00454-020-00240-w","project":[{"name":"Alpha Shape Theory Extended","call_identifier":"H2020","_id":"266A2E9E-B435-11E9-9278-68D0E5697425","grant_number":"788183"}],"isi":1,"quality_controlled":"1","main_file_link":[{"url":"https://arxiv.org/abs/1908.00856","open_access":"1"}],"oa":1,"external_id":{"arxiv":["1908.00856"],"isi":["000564488500002"]},"ec_funded":1,"volume":66,"date_created":"2020-09-06T22:01:13Z","date_updated":"2024-03-07T14:51:11Z","author":[{"id":"430D2C90-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2548-617X","first_name":"Arseniy","last_name":"Akopyan","full_name":"Akopyan, Arseniy"},{"first_name":"Alexander I.","last_name":"Bobenko","full_name":"Bobenko, Alexander I."},{"full_name":"Schief, Wolfgang K.","first_name":"Wolfgang K.","last_name":"Schief"},{"first_name":"Jan","last_name":"Techter","full_name":"Techter, Jan"}],"publisher":"Springer Nature","department":[{"_id":"HeEd"}],"publication_status":"published","year":"2021","acknowledgement":"This research was supported by the DFG Collaborative Research Center TRR 109 “Discretization in Geometry and Dynamics”. W.K.S. was also supported by the Australian Research Council (DP1401000851). A.V.A. was also supported by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant Agreement No. 78818 Alpha).","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"2021-10-01T00:00:00Z","page":"938-976","article_type":"original","citation":{"mla":"Akopyan, Arseniy, et al. “On Mutually Diagonal Nets on (Confocal) Quadrics and 3-Dimensional Webs.” Discrete and Computational Geometry, vol. 66, Springer Nature, 2021, pp. 938–76, doi:10.1007/s00454-020-00240-w.","short":"A. Akopyan, A.I. Bobenko, W.K. Schief, J. Techter, Discrete and Computational Geometry 66 (2021) 938–976.","chicago":"Akopyan, Arseniy, Alexander I. Bobenko, Wolfgang K. Schief, and Jan Techter. “On Mutually Diagonal Nets on (Confocal) Quadrics and 3-Dimensional Webs.” Discrete and Computational Geometry. Springer Nature, 2021. https://doi.org/10.1007/s00454-020-00240-w.","ama":"Akopyan A, Bobenko AI, Schief WK, Techter J. On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs. Discrete and Computational Geometry. 2021;66:938-976. doi:10.1007/s00454-020-00240-w","ista":"Akopyan A, Bobenko AI, Schief WK, Techter J. 2021. On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs. Discrete and Computational Geometry. 66, 938–976.","ieee":"A. Akopyan, A. I. Bobenko, W. K. Schief, and J. Techter, “On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs,” Discrete and Computational Geometry, vol. 66. Springer Nature, pp. 938–976, 2021.","apa":"Akopyan, A., Bobenko, A. I., Schief, W. K., & Techter, J. (2021). On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00240-w"},"publication":"Discrete and Computational Geometry","abstract":[{"text":"Canonical parametrisations of classical confocal coordinate systems are introduced and exploited to construct non-planar analogues of incircular (IC) nets on individual quadrics and systems of confocal quadrics. Intimate connections with classical deformations of quadrics that are isometric along asymptotic lines and circular cross-sections of quadrics are revealed. The existence of octahedral webs of surfaces of Blaschke type generated by asymptotic and characteristic lines that are diagonally related to lines of curvature is proved theoretically and established constructively. Appropriate samplings (grids) of these webs lead to three-dimensional extensions of non-planar IC nets. Three-dimensional octahedral grids composed of planes and spatially extending (checkerboard) IC-nets are shown to arise in connection with systems of confocal quadrics in Minkowski space. In this context, the Laguerre geometric notion of conical octahedral grids of planes is introduced. The latter generalise the octahedral grids derived from systems of confocal quadrics in Minkowski space. An explicit construction of conical octahedral grids is presented. The results are accompanied by various illustrations which are based on the explicit formulae provided by the theory.","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","intvolume":" 66","status":"public","title":"On mutually diagonal nets on (confocal) quadrics and 3-dimensional webs","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"8338"},{"ec_funded":1,"volume":66,"date_updated":"2024-03-07T14:54:59Z","date_created":"2020-08-11T07:11:51Z","author":[{"first_name":"Jean-Daniel","last_name":"Boissonnat","full_name":"Boissonnat, Jean-Daniel"},{"last_name":"Dyer","first_name":"Ramsay","full_name":"Dyer, Ramsay"},{"full_name":"Ghosh, Arijit","first_name":"Arijit","last_name":"Ghosh"},{"full_name":"Lieutier, Andre","first_name":"Andre","last_name":"Lieutier"},{"first_name":"Mathijs","last_name":"Wintraecken","id":"307CFBC8-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-7472-2220","full_name":"Wintraecken, Mathijs"}],"publisher":"Springer Nature","department":[{"_id":"HeEd"}],"publication_status":"published","year":"2021","acknowledgement":"Open access funding provided by the Institute of Science and Technology (IST Austria). Arijit Ghosh is supported by the Ramanujan Fellowship (No. SB/S2/RJN-064/2015), India.\r\nThis work has been funded by the European Research Council under the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). The third author is supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015), India. The fifth author also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411.","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"month":"09","language":[{"iso":"eng"}],"doi":"10.1007/s00454-020-00233-9","project":[{"name":"ISTplus - Postdoctoral Fellowships","call_identifier":"H2020","_id":"260C2330-B435-11E9-9278-68D0E5697425","grant_number":"754411"}],"quality_controlled":"1","isi":1,"external_id":{"isi":["000558119300001"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00454-020-00233-9"}],"abstract":[{"text":"We consider the following setting: suppose that we are given a manifold M in Rd with positive reach. Moreover assume that we have an embedded simplical complex A without boundary, whose vertex set lies on the manifold, is sufficiently dense and such that all simplices in A have sufficient quality. We prove that if, locally, interiors of the projection of the simplices onto the tangent space do not intersect, then A is a triangulation of the manifold, that is, they are homeomorphic.","lang":"eng"}],"type":"journal_article","oa_version":"Published Version","intvolume":" 66","status":"public","ddc":["510"],"title":"Local conditions for triangulating submanifolds of Euclidean space","_id":"8248","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","day":"01","scopus_import":"1","date_published":"2021-09-01T00:00:00Z","page":"666-686","article_type":"original","citation":{"chicago":"Boissonnat, Jean-Daniel, Ramsay Dyer, Arijit Ghosh, Andre Lieutier, and Mathijs Wintraecken. “Local Conditions for Triangulating Submanifolds of Euclidean Space.” Discrete and Computational Geometry. Springer Nature, 2021. https://doi.org/10.1007/s00454-020-00233-9.","short":"J.-D. Boissonnat, R. Dyer, A. Ghosh, A. Lieutier, M. Wintraecken, Discrete and Computational Geometry 66 (2021) 666–686.","mla":"Boissonnat, Jean-Daniel, et al. “Local Conditions for Triangulating Submanifolds of Euclidean Space.” Discrete and Computational Geometry, vol. 66, Springer Nature, 2021, pp. 666–86, doi:10.1007/s00454-020-00233-9.","ieee":"J.-D. Boissonnat, R. Dyer, A. Ghosh, A. Lieutier, and M. Wintraecken, “Local conditions for triangulating submanifolds of Euclidean space,” Discrete and Computational Geometry, vol. 66. Springer Nature, pp. 666–686, 2021.","apa":"Boissonnat, J.-D., Dyer, R., Ghosh, A., Lieutier, A., & Wintraecken, M. (2021). Local conditions for triangulating submanifolds of Euclidean space. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00233-9","ista":"Boissonnat J-D, Dyer R, Ghosh A, Lieutier A, Wintraecken M. 2021. Local conditions for triangulating submanifolds of Euclidean space. Discrete and Computational Geometry. 66, 666–686.","ama":"Boissonnat J-D, Dyer R, Ghosh A, Lieutier A, Wintraecken M. Local conditions for triangulating submanifolds of Euclidean space. Discrete and Computational Geometry. 2021;66:666-686. doi:10.1007/s00454-020-00233-9"},"publication":"Discrete and Computational Geometry"},{"type":"journal_article","abstract":[{"lang":"eng","text":"We investigate a sheaf-theoretic interpretation of stratification learning from geometric and topological perspectives. Our main result is the construction of stratification learning algorithms framed in terms of a sheaf on a partially ordered set with the Alexandroff topology. We prove that the resulting decomposition is the unique minimal stratification for which the strata are homogeneous and the given sheaf is constructible. In particular, when we choose to work with the local homology sheaf, our algorithm gives an alternative to the local homology transfer algorithm given in Bendich et al. (Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1355–1370, ACM, New York, 2012), and the cohomology stratification algorithm given in Nanda (Found. Comput. Math. 20(2), 195–222, 2020). Additionally, we give examples of stratifications based on the geometric techniques of Breiding et al. (Rev. Mat. Complut. 31(3), 545–593, 2018), illustrating how the sheaf-theoretic approach can be used to study stratifications from both topological and geometric perspectives. This approach also points toward future applications of sheaf theory in the study of topological data analysis by illustrating the utility of the language of sheaf theory in generalizing existing algorithms."}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"7905","ddc":["510"],"title":"Sheaf-theoretic stratification learning from geometric and topological perspectives","status":"public","intvolume":" 65","file":[{"access_level":"open_access","file_name":"2020_DiscreteCompGeometry_Brown.pdf","creator":"dernst","content_type":"application/pdf","file_size":1013730,"file_id":"8803","relation":"main_file","success":1,"checksum":"487a84ea5841b75f04f66d7ebd71b67e","date_updated":"2020-11-25T09:06:41Z","date_created":"2020-11-25T09:06:41Z"}],"oa_version":"Published Version","scopus_import":"1","day":"01","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","publication":"Discrete and Computational Geometry","citation":{"ieee":"A. Brown and B. Wang, “Sheaf-theoretic stratification learning from geometric and topological perspectives,” Discrete and Computational Geometry, vol. 65. Springer Nature, pp. 1166–1198, 2021.","apa":"Brown, A., & Wang, B. (2021). Sheaf-theoretic stratification learning from geometric and topological perspectives. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-020-00206-y","ista":"Brown A, Wang B. 2021. Sheaf-theoretic stratification learning from geometric and topological perspectives. Discrete and Computational Geometry. 65, 1166–1198.","ama":"Brown A, Wang B. Sheaf-theoretic stratification learning from geometric and topological perspectives. Discrete and Computational Geometry. 2021;65:1166-1198. doi:10.1007/s00454-020-00206-y","chicago":"Brown, Adam, and Bei Wang. “Sheaf-Theoretic Stratification Learning from Geometric and Topological Perspectives.” Discrete and Computational Geometry. Springer Nature, 2021. https://doi.org/10.1007/s00454-020-00206-y.","short":"A. Brown, B. Wang, Discrete and Computational Geometry 65 (2021) 1166–1198.","mla":"Brown, Adam, and Bei Wang. “Sheaf-Theoretic Stratification Learning from Geometric and Topological Perspectives.” Discrete and Computational Geometry, vol. 65, Springer Nature, 2021, pp. 1166–98, doi:10.1007/s00454-020-00206-y."},"article_type":"original","page":"1166-1198","date_published":"2021-06-01T00:00:00Z","file_date_updated":"2020-11-25T09:06:41Z","year":"2021","acknowledgement":"Open access funding provided by Institute of Science and Technology (IST Austria). This work was partially supported by NSF IIS-1513616 and NSF ABI-1661375. The authors would like to thank the anonymous referees for their insightful comments.","publication_status":"published","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"author":[{"last_name":"Brown","first_name":"Adam","id":"70B7FDF6-608D-11E9-9333-8535E6697425","full_name":"Brown, Adam"},{"first_name":"Bei","last_name":"Wang","full_name":"Wang, Bei"}],"date_updated":"2024-03-07T15:01:58Z","date_created":"2020-05-30T10:26:04Z","volume":65,"month":"06","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1712.07734"],"isi":["000536324700001"]},"oa":1,"quality_controlled":"1","isi":1,"project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"doi":"10.1007/s00454-020-00206-y","language":[{"iso":"eng"}]},{"issue":"4","abstract":[{"text":"Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.","lang":"eng"}],"type":"journal_article","oa_version":"Published Version","file":[{"file_id":"5988","relation":"main_file","date_updated":"2020-07-14T12:47:14Z","date_created":"2019-02-14T11:57:22Z","checksum":"e1bff88f1d77001b53b78c485ce048d7","file_name":"2018_DiscreteGeometry_Lubiw.pdf","access_level":"open_access","creator":"dernst","file_size":556276,"content_type":"application/pdf"}],"intvolume":" 61","ddc":["000"],"title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","status":"public","_id":"5986","user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","has_accepted_license":"1","article_processing_charge":"Yes (via OA deal)","day":"01","scopus_import":"1","date_published":"2019-06-01T00:00:00Z","page":"880-898","article_type":"original","citation":{"ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. 2019;61(4):880-898. doi:10.1007/s00454-018-0035-8","ista":"Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. 61(4), 880–898.","apa":"Lubiw, A., Masárová, Z., & Wagner, U. (2019). A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete & Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-018-0035-8","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge-labelled triangulations,” Discrete & Computational Geometry, vol. 61, no. 4. Springer Nature, pp. 880–898, 2019.","mla":"Lubiw, Anna, et al. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry, vol. 61, no. 4, Springer Nature, 2019, pp. 880–98, doi:10.1007/s00454-018-0035-8.","short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete & Computational Geometry 61 (2019) 880–898.","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” Discrete & Computational Geometry. Springer Nature, 2019. https://doi.org/10.1007/s00454-018-0035-8."},"publication":"Discrete & Computational Geometry","file_date_updated":"2020-07-14T12:47:14Z","volume":61,"date_created":"2019-02-14T11:54:08Z","date_updated":"2023-09-07T13:17:36Z","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"683"},{"relation":"dissertation_contains","status":"public","id":"7944"}]},"author":[{"full_name":"Lubiw, Anna","last_name":"Lubiw","first_name":"Anna"},{"orcid":"0000-0002-6660-1322","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","last_name":"Masárová","first_name":"Zuzana","full_name":"Masárová, Zuzana"},{"full_name":"Wagner, Uli","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87","last_name":"Wagner","first_name":"Uli"}],"publisher":"Springer Nature","department":[{"_id":"UlWa"}],"publication_status":"published","year":"2019","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"month":"06","language":[{"iso":"eng"}],"doi":"10.1007/s00454-018-0035-8","project":[{"name":"IST Austria Open Access Fund","_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854"}],"quality_controlled":"1","isi":1,"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"external_id":{"arxiv":["1710.02741"],"isi":["000466130000009"]},"oa":1},{"oa_version":"Published Version","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"2815","title":"Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions","status":"public","intvolume":" 49","abstract":[{"lang":"eng","text":"The fact that a sum of isotropic Gaussian kernels can have more modes than kernels is surprising. Extra (ghost) modes do not exist in ℝ1 and are generally not well studied in higher dimensions. We study a configuration of n+1 Gaussian kernels for which there are exactly n+2 modes. We show that all modes lie on a finite set of lines, which we call axes, and study the restriction of the Gaussian mixture to these axes in order to discover that there are an exponential number of critical points in this configuration. Although the existence of ghost modes remained unknown due to the difficulty of finding examples in ℝ2, we show that the resilience of ghost modes grows like the square root of the dimension. In addition, we exhibit finite configurations of isotropic Gaussian kernels with superlinearly many modes."}],"issue":"4","type":"journal_article","date_published":"2013-06-01T00:00:00Z","publication":"Discrete & Computational Geometry","citation":{"ama":"Edelsbrunner H, Fasy BT, Rote G. Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions. Discrete & Computational Geometry. 2013;49(4):797-822. doi:10.1007/s00454-013-9517-x","ista":"Edelsbrunner H, Fasy BT, Rote G. 2013. Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions. Discrete & Computational Geometry. 49(4), 797–822.","apa":"Edelsbrunner, H., Fasy, B. T., & Rote, G. (2013). Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-013-9517-x","ieee":"H. Edelsbrunner, B. T. Fasy, and G. Rote, “Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions,” Discrete & Computational Geometry, vol. 49, no. 4. Springer, pp. 797–822, 2013.","mla":"Edelsbrunner, Herbert, et al. “Add Isotropic Gaussian Kernels at Own Risk: More and More Resilient Modes in Higher Dimensions.” Discrete & Computational Geometry, vol. 49, no. 4, Springer, 2013, pp. 797–822, doi:10.1007/s00454-013-9517-x.","short":"H. Edelsbrunner, B.T. Fasy, G. Rote, Discrete & Computational Geometry 49 (2013) 797–822.","chicago":"Edelsbrunner, Herbert, Brittany Terese Fasy, and Günter Rote. “Add Isotropic Gaussian Kernels at Own Risk: More and More Resilient Modes in Higher Dimensions.” Discrete & Computational Geometry. Springer, 2013. https://doi.org/10.1007/s00454-013-9517-x."},"article_type":"original","page":"797 - 822","day":"01","article_processing_charge":"No","scopus_import":"1","author":[{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"full_name":"Fasy, Brittany Terese","id":"F65D502E-E68D-11E9-9252-C644099818F6","first_name":"Brittany Terese","last_name":"Fasy"},{"first_name":"Günter","last_name":"Rote","full_name":"Rote, Günter"}],"related_material":{"record":[{"id":"3134","relation":"earlier_version","status":"public"}]},"date_updated":"2023-02-23T11:13:49Z","date_created":"2018-12-11T11:59:44Z","volume":49,"year":"2013","acknowledgement":"This research is partially supported by the National Science Foundation (NSF) under Grant DBI-0820624, by the European Science Foundation under the Research Networking Programme, and the Russian Government Project 11.G34.31.0053.","publication_status":"published","department":[{"_id":"HeEd"}],"publisher":"Springer","publist_id":"3991","doi":"10.1007/s00454-013-9517-x","language":[{"iso":"eng"}],"main_file_link":[{"open_access":"1","url":"https://doi.org/10.1007/s00454-013-9517-x"}],"oa":1,"quality_controlled":"1","month":"06","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]}},{"acknowledgement":"The first, second, and fourth authors acknowledge support from the Center for Discrete Mathematics and Theoretical Computer Science (DIMACS), a National Science Foundation Science and Technology Center under NSF Grant STC 88-09648. The second author's work was supported by the National Science Foundation under Grant CCR-8714565. The third author's work was supported by the Deutsche Forschungsgemeinschaft under Grant A1 253/1-3, Schwerpunktprogramm \"Datenstrukturen und effiziente Algorithmen.\" The last two authors' work was also partially supported by the ESPRIT II Basic Research Action of the EC under Contract No. 3075 (project ALCOM).","year":"1991","publisher":"Springer","publication_status":"published","author":[{"first_name":"Pankaj","last_name":"Agarwal","full_name":"Agarwal, Pankaj"},{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"full_name":"Schwarzkopf, Otfried","first_name":"Otfried","last_name":"Schwarzkopf"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"volume":6,"date_created":"2018-12-11T12:06:42Z","date_updated":"2022-02-24T15:06:41Z","publist_id":"2062","extern":"1","oa":1,"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02574698","open_access":"1"}],"quality_controlled":"1","doi":"10.1007/BF02574698","language":[{"iso":"eng"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"12","_id":"4061","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","intvolume":" 6","status":"public","title":"Euclidean minimum spanning trees and bichromatic closest pairs","oa_version":"Published Version","type":"journal_article","issue":"1","abstract":[{"lang":"eng","text":"We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of N points in Ed in time O(Fd (N,N) logd N), where Fd (n,m) is the time required to compute a bichromatic closest pair among n red and m green points in Ed . If Fd (N,N)=Ω(N1+ε), for some fixed e{open}>0, then the running time improves to O(Fd (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected time O((nm log n log m)2/3+m log2 n+n log2 m) in E3, which yields an O(N4/3 log4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree of N points in E3. In d≥4 dimensions we obtain expected time O((nm)1-1/([d/2]+1)+ε+m log n+n log m) for the bichromatic closest pair problem and O(N2-2/([d/2]+1)ε) for the Euclidean minimum spanning tree problem, for any positive e{open}."}],"citation":{"ama":"Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Computational Geometry. 1991;6(1):407-422. doi:10.1007/BF02574698","apa":"Agarwal, P., Edelsbrunner, H., Schwarzkopf, O., & Welzl, E. (1991). Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02574698","ieee":"P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “Euclidean minimum spanning trees and bichromatic closest pairs,” Discrete & Computational Geometry, vol. 6, no. 1. Springer, pp. 407–422, 1991.","ista":"Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. 1991. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete & Computational Geometry. 6(1), 407–422.","short":"P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, Discrete & Computational Geometry 6 (1991) 407–422.","mla":"Agarwal, Pankaj, et al. “Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” Discrete & Computational Geometry, vol. 6, no. 1, Springer, 1991, pp. 407–22, doi:10.1007/BF02574698.","chicago":"Agarwal, Pankaj, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. “Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” Discrete & Computational Geometry. Springer, 1991. https://doi.org/10.1007/BF02574698."},"publication":"Discrete & Computational Geometry","page":"407 - 422","article_type":"original","date_published":"1991-12-01T00:00:00Z","scopus_import":"1","article_processing_charge":"No","day":"01"},{"scopus_import":"1","day":"01","article_processing_charge":"No","publication":"Discrete & Computational Geometry","citation":{"ama":"Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. Points and triangles in the plane and halving planes in space. Discrete & Computational Geometry. 1991;6(1):435-442. doi:10.1007/BF02574700","ieee":"B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, and R. Wenger, “Points and triangles in the plane and halving planes in space,” Discrete & Computational Geometry, vol. 6, no. 1. Springer, pp. 435–442, 1991.","apa":"Aronov, B., Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., & Wenger, R. (1991). Points and triangles in the plane and halving planes in space. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02574700","ista":"Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. 1991. Points and triangles in the plane and halving planes in space. Discrete & Computational Geometry. 6(1), 435–442.","short":"B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, R. Wenger, Discrete & Computational Geometry 6 (1991) 435–442.","mla":"Aronov, Boris, et al. “Points and Triangles in the Plane and Halving Planes in Space.” Discrete & Computational Geometry, vol. 6, no. 1, Springer, 1991, pp. 435–42, doi:10.1007/BF02574700.","chicago":"Aronov, Boris, Bernard Chazelle, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Rephael Wenger. “Points and Triangles in the Plane and Halving Planes in Space.” Discrete & Computational Geometry. Springer, 1991. https://doi.org/10.1007/BF02574700."},"article_type":"original","page":"435 - 442","date_published":"1991-12-01T00:00:00Z","type":"journal_article","abstract":[{"text":"We prove that for any set S of n points in the plane and n3-α triangles spanned by the points in S there exists a point (not necessarily in S) contained in at least n3-3α/(c log5 n) of the triangles. This implies that any set of n points in three-dimensional space defines at most {Mathematical expression} halving planes.","lang":"eng"}],"issue":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4062","status":"public","title":"Points and triangles in the plane and halving planes in space","intvolume":" 6","oa_version":"Published Version","month":"12","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02574700","open_access":"1"}],"oa":1,"quality_controlled":"1","doi":"10.1007/BF02574700","language":[{"iso":"eng"}],"publist_id":"2063","extern":"1","acknowledgement":"Work on this paper by Boris Aronov and Rephael Wenger has been supported by DIMACS under NSF Grant STC-88-09648. Work on this paper by Bernard Chazelle has been supported by NSF Grant CCR-87-00917. Work by Herbert Edelsbrunner has been supported by NSF Grant CCR-87-14565. Micha Sharir has been supported by ONR Grant N00014-87-K-0129, by NSF Grant CCR-89-01484, and by grants from the U.S.-Israeli Binational Science Foundation, the Israeli National Council for Research and Development, and the Fund for Basic Research administered by the Israeli\r\nAcademy of Sciences","year":"1991","publication_status":"published","publisher":"Springer","author":[{"first_name":"Boris","last_name":"Aronov","full_name":"Aronov, Boris"},{"first_name":"Bernard","last_name":"Chazelle","full_name":"Chazelle, Bernard"},{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"last_name":"Sharir","first_name":"Micha","full_name":"Sharir, Micha"},{"full_name":"Wenger, Rephael","last_name":"Wenger","first_name":"Rephael"}],"date_updated":"2022-02-24T15:39:25Z","date_created":"2018-12-11T12:06:43Z","volume":6},{"month":"03","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187785"}],"quality_controlled":"1","doi":"10.1007/BF02187785","language":[{"iso":"eng"}],"publist_id":"2054","extern":"1","acknowledgement":"Supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by NSF Grant CCR-8714565. Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. I-6-44862 and by NSF Grant CCR-87t4565. Work by the third author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant DCR-82-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD--the Israeli National Council for Research and Development. An abstract of this\r\npaper has appeared in the Proceedings of the 13th International Mathematical Programming Symposium, Tokyo, 1988, p. 147","year":"1990","publication_status":"published","publisher":"Springer","author":[{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"}],"date_created":"2018-12-11T12:06:44Z","date_updated":"2022-02-22T11:02:41Z","volume":5,"scopus_import":"1","day":"01","article_processing_charge":"No","publication":"Discrete & Computational Geometry","citation":{"ama":"Edelsbrunner H, Guibas L, Sharir M. The complexity of many cells in arrangements of planes and related problems. Discrete & Computational Geometry. 1990;5(1):197-216. doi:10.1007/BF02187785","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity of many cells in arrangements of planes and related problems,” Discrete & Computational Geometry, vol. 5, no. 1. Springer, pp. 197–216, 1990.","apa":"Edelsbrunner, H., Guibas, L., & Sharir, M. (1990). The complexity of many cells in arrangements of planes and related problems. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187785","ista":"Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity of many cells in arrangements of planes and related problems. Discrete & Computational Geometry. 5(1), 197–216.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & Computational Geometry 5 (1990) 197–216.","mla":"Edelsbrunner, Herbert, et al. “The Complexity of Many Cells in Arrangements of Planes and Related Problems.” Discrete & Computational Geometry, vol. 5, no. 1, Springer, 1990, pp. 197–216, doi:10.1007/BF02187785.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity of Many Cells in Arrangements of Planes and Related Problems.” Discrete & Computational Geometry. Springer, 1990. https://doi.org/10.1007/BF02187785."},"article_type":"original","page":"197 - 216","date_published":"1990-03-01T00:00:00Z","type":"journal_article","abstract":[{"text":"We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m 2/3 n logn +n 2); we can calculatem such cells specified by a point in each, in worst-case timeO(m 2/3 n log3 n+n 2 logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m 2/3 n logn+n 2), but this number is onlyO(m 3/5– n 4/5+2 +m+n logm), for any>0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m 3/4– n 3/4+3 +m) log2 n+n logn logm) for any>0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m 3/4– n 3/4+3 +m] log2 n+n logn logm) for any>0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d>3, isO(m 2/3 n d/3 logn+n d–1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.","lang":"eng"}],"issue":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4066","status":"public","title":"The complexity of many cells in arrangements of planes and related problems","intvolume":" 5","oa_version":"None"},{"language":[{"iso":"eng"}],"doi":"10.1007/BF02187784","quality_controlled":"1","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187784"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"01","volume":5,"date_updated":"2022-02-22T09:27:30Z","date_created":"2018-12-11T12:06:46Z","author":[{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"last_name":"Guibas","first_name":"Leonidas","full_name":"Guibas, Leonidas"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"}],"publisher":"Springer","publication_status":"published","year":"1990","acknowledgement":"The first author is pleased to acknowledge partial support by the Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and the National Science Foundation under Grant CCR-8714565. Work on this paper by the third author has been supported by Office of Naval Research Grant N00014-82-K-0381, by National Science Foundation Grant DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD-the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 4th ACM Symposium on Computational Geometry, 1988, pp. 44–55.","extern":"1","publist_id":"2053","date_published":"1990-01-01T00:00:00Z","page":"161 - 196","article_type":"original","citation":{"chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” Discrete & Computational Geometry. Springer, 1990. https://doi.org/10.1007/BF02187784.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & Computational Geometry 5 (1990) 161–196.","mla":"Edelsbrunner, Herbert, et al. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” Discrete & Computational Geometry, vol. 5, no. 1, Springer, 1990, pp. 161–96, doi:10.1007/BF02187784.","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity and construction of many faces in arrangements of lines and of segments,” Discrete & Computational Geometry, vol. 5, no. 1. Springer, pp. 161–196, 1990.","apa":"Edelsbrunner, H., Guibas, L., & Sharir, M. (1990). The complexity and construction of many faces in arrangements of lines and of segments. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187784","ista":"Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity and construction of many faces in arrangements of lines and of segments. Discrete & Computational Geometry. 5(1), 161–196.","ama":"Edelsbrunner H, Guibas L, Sharir M. The complexity and construction of many faces in arrangements of lines and of segments. Discrete & Computational Geometry. 1990;5(1):161-196. doi:10.1007/BF02187784"},"publication":"Discrete & Computational Geometry","article_processing_charge":"No","day":"01","scopus_import":"1","oa_version":"None","intvolume":" 5","status":"public","title":"The complexity and construction of many faces in arrangements of lines and of segments","_id":"4072","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","issue":"1","abstract":[{"lang":"eng","text":"We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m 2/3– n 2/3+2 +n) for any>0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m 2/3– n 2/3+2 logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m 2/3– n 2/3+2 +n (n) logm) for any>0, where(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m 2/3– n 2/3+2 log+n(n) log2 n logm)."}],"type":"journal_article"},{"quality_controlled":"1","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187778"}],"language":[{"iso":"eng"}],"doi":"10.1007/BF02187778","month":"01","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publication_status":"published","publisher":"Springer","year":"1990","acknowledgement":"Research of the first author was supported by Amoco Foundation for Faculty Development in Computer Science Grant No. 1-6-44862. Work on this paper by the second author was supported by Office of Naval Research Grant No. N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation.","date_updated":"2022-02-22T14:50:34Z","date_created":"2018-12-11T12:06:45Z","volume":5,"author":[{"last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"}],"extern":"1","publist_id":"2057","article_type":"original","page":"35 - 42","publication":"Discrete & Computational Geometry","citation":{"chicago":"Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” Discrete & Computational Geometry. Springer, 1990. https://doi.org/10.1007/BF02187778.","short":"H. Edelsbrunner, M. Sharir, Discrete & Computational Geometry 5 (1990) 35–42.","mla":"Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” Discrete & Computational Geometry, vol. 5, no. 1, Springer, 1990, pp. 35–42, doi:10.1007/BF02187778.","apa":"Edelsbrunner, H., & Sharir, M. (1990). The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187778","ieee":"H. Edelsbrunner and M. Sharir, “The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2,” Discrete & Computational Geometry, vol. 5, no. 1. Springer, pp. 35–42, 1990.","ista":"Edelsbrunner H, Sharir M. 1990. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. Discrete & Computational Geometry. 5(1), 35–42.","ama":"Edelsbrunner H, Sharir M. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. Discrete & Computational Geometry. 1990;5(1):35-42. doi:10.1007/BF02187778"},"date_published":"1990-01-01T00:00:00Z","day":"01","article_processing_charge":"No","title":"The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2","status":"public","intvolume":" 5","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4068","oa_version":"None","type":"journal_article","abstract":[{"lang":"eng","text":"LetS be a collection ofn convex, closed, and pairwise nonintersecting sets in the Euclidean plane labeled from 1 ton. A pair of permutations\r\n(i1i2in−1in)(inin−1i2i1) \r\nis called ageometric permutation of S if there is a line that intersects all sets ofS in this order. We prove thatS can realize at most 2n–2 geometric permutations. This upper bound is tight."}],"issue":"1"},{"date_published":"1990-03-01T00:00:00Z","page":"99 - 160","article_type":"original","citation":{"chicago":"Clarkson, Kenneth, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Emo Welzl. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” Discrete & Computational Geometry. Springer, 1990. https://doi.org/10.1007/BF02187783.","short":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Discrete & Computational Geometry 5 (1990) 99–160.","mla":"Clarkson, Kenneth, et al. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” Discrete & Computational Geometry, vol. 5, no. 1, Springer, 1990, pp. 99–160, doi:10.1007/BF02187783.","ieee":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, “Combinatorial complexity bounds for arrangements of curves and spheres,” Discrete & Computational Geometry, vol. 5, no. 1. Springer, pp. 99–160, 1990.","apa":"Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., & Welzl, E. (1990). Combinatorial complexity bounds for arrangements of curves and spheres. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187783","ista":"Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. 1990. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete & Computational Geometry. 5(1), 99–160.","ama":"Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete & Computational Geometry. 1990;5(1):99-160. doi:10.1007/BF02187783"},"publication":"Discrete & Computational Geometry","article_processing_charge":"No","day":"01","oa_version":"None","intvolume":" 5","title":"Combinatorial complexity bounds for arrangements of curves and spheres","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4074","issue":"1","abstract":[{"lang":"eng","text":"We present upper and lower bounds for extremal problems defined for arrangements of lines, circles, spheres, and alike. For example, we prove that the maximum number of edges boundingm cells in an arrangement ofn lines is Θ(m 2/3 n 2/3 +n), and that it isO(m 2/3 n 2/3 β(n) +n) forn unit-circles, whereβ(n) (and laterβ(m, n)) is a function that depends on the inverse of Ackermann's function and grows extremely slowly. If we replace unit-circles by circles of arbitrary radii the upper bound goes up toO(m 3/5 n 4/5 β(n) +n). The same bounds (without theβ(n)-terms) hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees in arrangements of lines and of unit-circles our bounds match previous results, but our proofs are considerably simpler than the previous ones. The maximum sum of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m 4/7 n 9/7 β(m, n) +n 2), in general, andO(m 3/4 n 3/4 β(m, n) +n) if no three spheres intersect in a common circle. The latter bound implies that the maximum number of unit-distances amongm points in three dimensions isO(m 3/2 β(m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given."}],"type":"journal_article","language":[{"iso":"eng"}],"doi":"10.1007/BF02187783","quality_controlled":"1","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187783"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"month":"03","volume":5,"date_updated":"2022-02-17T15:41:04Z","date_created":"2018-12-11T12:06:47Z","author":[{"full_name":"Clarkson, Kenneth","last_name":"Clarkson","first_name":"Kenneth"},{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"full_name":"Sharir, Micha","first_name":"Micha","last_name":"Sharir"},{"last_name":"Welzl","first_name":"Emo","full_name":"Welzl, Emo"}],"publisher":"Springer","publication_status":"published","year":"1990","acknowledgement":"The research of the second author was supported by the National Science Foundation under Grant CCR-8714565. Work by the fourth author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a research grant from the NCRD, the Israeli National Council for Research and Development. A preliminary version of this paper has appeared in theProceedings of the 29th IEEE Symposium on Foundations of Computer Science, 1988.","extern":"1","publist_id":"2048"},{"type":"journal_article","issue":"1","abstract":[{"text":"Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions, calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly, using subquadratic space and preprocessing, so that, given any query pointp, we can calculate efficiently the face containingp. First, we consider the case of lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: (1) given a set ofn points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, (2) given a simple polygonal path , form a data structure from which we can find the convex hull of any subpath of quickly, and (3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a tradeoff between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing time. Lastly, we note that our techniques allow us to computem faces in an arrangement ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal.","lang":"eng"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4088","intvolume":" 4","title":"Implicitly representing arrangements of lines or segments","status":"public","oa_version":"Published Version","scopus_import":"1","article_processing_charge":"No","day":"01","citation":{"chicago":"Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, Raimund Seidel, Micha Sharir, Jack Snoeyink, and Emo Welzl. “Implicitly Representing Arrangements of Lines or Segments.” Discrete & Computational Geometry. Springer, 1989. https://doi.org/10.1007/BF02187742.","mla":"Edelsbrunner, Herbert, et al. “Implicitly Representing Arrangements of Lines or Segments.” Discrete & Computational Geometry, vol. 4, no. 1, Springer, 1989, pp. 433–66, doi:10.1007/BF02187742.","short":"H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, E. Welzl, Discrete & Computational Geometry 4 (1989) 433–466.","ista":"Edelsbrunner H, Guibas L, Hershberger J, Seidel R, Sharir M, Snoeyink J, Welzl E. 1989. Implicitly representing arrangements of lines or segments. Discrete & Computational Geometry. 4(1), 433–466.","apa":"Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., Sharir, M., Snoeyink, J., & Welzl, E. (1989). Implicitly representing arrangements of lines or segments. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187742","ieee":"H. Edelsbrunner et al., “Implicitly representing arrangements of lines or segments,” Discrete & Computational Geometry, vol. 4, no. 1. Springer, pp. 433–466, 1989.","ama":"Edelsbrunner H, Guibas L, Hershberger J, et al. Implicitly representing arrangements of lines or segments. Discrete & Computational Geometry. 1989;4(1):433-466. doi:10.1007/BF02187742"},"publication":"Discrete & Computational Geometry","page":"433 - 466","article_type":"original","date_published":"1989-12-01T00:00:00Z","publist_id":"2036","extern":"1","year":"1989","acknowledgement":"The first author is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565. Work on this paper by the fifth author has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085, by grants from the Digital Equipment Corporation, and the IBM Corporation, and by a research grant from the NCRD—the Israeli National Council for Research and Development. The sixth author was supported in part by a National Science Foundation Graduate Fellowship. This work was begun while the non-DEC authors were visiting at the DEC Systems Research Center.","publisher":"Springer","publication_status":"published","author":[{"first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"full_name":"Hershberger, John","first_name":"John","last_name":"Hershberger"},{"last_name":"Seidel","first_name":"Raimund","full_name":"Seidel, Raimund"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"},{"last_name":"Snoeyink","first_name":"Jack","full_name":"Snoeyink, Jack"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}],"volume":4,"date_created":"2018-12-11T12:06:52Z","date_updated":"2022-02-10T15:03:48Z","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"12","oa":1,"main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02187742"}],"quality_controlled":"1","doi":"10.1007/BF02187742","language":[{"iso":"eng"}]},{"scopus_import":"1","article_processing_charge":"No","day":"01","page":"523 - 539","article_type":"original","citation":{"ista":"Edelsbrunner H, Guibas L, Hershberger J, Pach J, Pollack R, Seidel R, Sharir M, Snoeyink J. 1989. On arrangements of Jordan arcs with three intersections per pair. Discrete & Computational Geometry. 4(1), 523–539.","apa":"Edelsbrunner, H., Guibas, L., Hershberger, J., Pach, J., Pollack, R., Seidel, R., … Snoeyink, J. (1989). On arrangements of Jordan arcs with three intersections per pair. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187745","ieee":"H. Edelsbrunner et al., “On arrangements of Jordan arcs with three intersections per pair,” Discrete & Computational Geometry, vol. 4, no. 1. Springer, pp. 523–539, 1989.","ama":"Edelsbrunner H, Guibas L, Hershberger J, et al. On arrangements of Jordan arcs with three intersections per pair. Discrete & Computational Geometry. 1989;4(1):523-539. doi:10.1007/BF02187745","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, János Pach, Richard Pollack, Raimund Seidel, Micha Sharir, and Jack Snoeyink. “On Arrangements of Jordan Arcs with Three Intersections per Pair.” Discrete & Computational Geometry. Springer, 1989. https://doi.org/10.1007/BF02187745.","mla":"Edelsbrunner, Herbert, et al. “On Arrangements of Jordan Arcs with Three Intersections per Pair.” Discrete & Computational Geometry, vol. 4, no. 1, Springer, 1989, pp. 523–39, doi:10.1007/BF02187745.","short":"H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel, M. Sharir, J. Snoeyink, Discrete & Computational Geometry 4 (1989) 523–539."},"publication":"Discrete & Computational Geometry","date_published":"1989-12-01T00:00:00Z","type":"journal_article","issue":"1","abstract":[{"text":"Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union ofn regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan acrs in the upper halfplane starting and ending on thex-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only (n(n)), where(n) is the extremely slowly growing functional inverse of Ackermann's function.","lang":"eng"}],"intvolume":" 4","title":"On arrangements of Jordan arcs with three intersections per pair","status":"public","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4089","oa_version":"Published Version","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"12","quality_controlled":"1","oa":1,"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187745","open_access":"1"}],"language":[{"iso":"eng"}],"doi":"10.1007/BF02187745","extern":"1","publist_id":"2037","publisher":"Springer","publication_status":"published","acknowledgement":"The first author is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and National Science Foundation Grant CCR-8714565. Work on this paper by the fourth and seventh authors has been supported by Office of Naval Research Grant N00014-87-K-0129, by National Science Foundation Grant NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation and the IBM Corporation. The seventh author in addition wishes to acknowledge support by a research grant from the NCRD—the Israeli National Council for Research and Development. The fifth author would like to acknowledge support in part by NSF grant DMS-8501947. Finally, the eighth author was supported in part by a National Science Foundation Graduate Fellowship.","year":"1989","volume":4,"date_updated":"2022-02-10T15:40:04Z","date_created":"2018-12-11T12:06:52Z","author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"},{"first_name":"John","last_name":"Hershberger","full_name":"Hershberger, John"},{"full_name":"Pach, János","last_name":"Pach","first_name":"János"},{"first_name":"Richard","last_name":"Pollack","full_name":"Pollack, Richard"},{"last_name":"Seidel","first_name":"Raimund","full_name":"Seidel, Raimund"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"},{"first_name":"Jack","last_name":"Snoeyink","full_name":"Snoeyink, Jack"}]},{"scopus_import":"1","article_processing_charge":"No","day":"01","page":"337 - 343","article_type":"original","citation":{"chicago":"Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces .” Discrete & Computational Geometry. Springer, 1989. https://doi.org/10.1007/BF02187734.","mla":"Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces .” Discrete & Computational Geometry, vol. 4, no. 4, Springer, 1989, pp. 337–43, doi:10.1007/BF02187734.","short":"H. Edelsbrunner, Discrete & Computational Geometry 4 (1989) 337–343.","ista":"Edelsbrunner H. 1989. The upper envelope of piecewise linear functions: Tight bounds on the number of faces . Discrete & Computational Geometry. 4(4), 337–343.","apa":"Edelsbrunner, H. (1989). The upper envelope of piecewise linear functions: Tight bounds on the number of faces . Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187734","ieee":"H. Edelsbrunner, “The upper envelope of piecewise linear functions: Tight bounds on the number of faces ,” Discrete & Computational Geometry, vol. 4, no. 4. Springer, pp. 337–343, 1989.","ama":"Edelsbrunner H. The upper envelope of piecewise linear functions: Tight bounds on the number of faces . Discrete & Computational Geometry. 1989;4(4):337-343. doi:10.1007/BF02187734"},"publication":"Discrete & Computational Geometry","date_published":"1989-11-01T00:00:00Z","type":"journal_article","issue":"4","abstract":[{"text":"This note proves that the maximum number of faces (of any dimension) of the upper envelope of a set ofn possibly intersectingd-simplices ind+1 dimensions is (n d (n)). This is an extension of a result of Pach and Sharir [PS] who prove the same bound for the number ofd-dimensional faces of the upper envelope.","lang":"eng"}],"intvolume":" 4","status":"public","title":"The upper envelope of piecewise linear functions: Tight bounds on the number of faces ","_id":"4086","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","oa_version":"Published Version","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"month":"11","quality_controlled":"1","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187734","open_access":"1"}],"oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/BF02187734","extern":"1","publist_id":"2034","publisher":"Springer","publication_status":"published","year":"1989","acknowledgement":"This work was supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862 and by the National Science Foundation under Grant CCR-8714565. Research on the presented result was partially carried out while the author worked for the IBM T. J. Watson Research Center at Yorktown Height, New York, USA. \r\n","volume":4,"date_updated":"2022-02-10T11:08:12Z","date_created":"2018-12-11T12:06:51Z","author":[{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}]},{"main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02187733"}],"oa":1,"quality_controlled":"1","doi":"10.1007/BF02187733","language":[{"iso":"eng"}],"month":"12","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"year":"1989","acknowledgement":"Work on this paper by the first author has been supported by Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862. Work by the third author has been supported by the Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, by grants from the Digital Equipment Corporation and the IBM Corporation, and by a research grant from NCRD, the Israeli National Council for Research and Development.","publication_status":"published","publisher":"Springer","author":[{"first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"full_name":"Guibas, Leonidas","last_name":"Guibas","first_name":"Leonidas"},{"last_name":"Sharir","first_name":"Micha","full_name":"Sharir, Micha"}],"date_created":"2018-12-11T12:06:50Z","date_updated":"2022-02-10T15:53:48Z","volume":4,"publist_id":"2038","extern":"1","publication":"Discrete & Computational Geometry","citation":{"ama":"Edelsbrunner H, Guibas L, Sharir M. The upper envelope of piecewise linear functions: Algorithms and applications. Discrete & Computational Geometry. 1989;4(1):311-336. doi:10.1007/BF02187733","ista":"Edelsbrunner H, Guibas L, Sharir M. 1989. The upper envelope of piecewise linear functions: Algorithms and applications. Discrete & Computational Geometry. 4(1), 311–336.","apa":"Edelsbrunner, H., Guibas, L., & Sharir, M. (1989). The upper envelope of piecewise linear functions: Algorithms and applications. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187733","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The upper envelope of piecewise linear functions: Algorithms and applications,” Discrete & Computational Geometry, vol. 4, no. 1. Springer, pp. 311–336, 1989.","mla":"Edelsbrunner, Herbert, et al. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” Discrete & Computational Geometry, vol. 4, no. 1, Springer, 1989, pp. 311–36, doi:10.1007/BF02187733.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete & Computational Geometry 4 (1989) 311–336.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” Discrete & Computational Geometry. Springer, 1989. https://doi.org/10.1007/BF02187733."},"article_type":"original","page":"311 - 336","date_published":"1989-12-01T00:00:00Z","day":"01","article_processing_charge":"No","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4081","status":"public","title":"The upper envelope of piecewise linear functions: Algorithms and applications","intvolume":" 4","oa_version":"Published Version","type":"journal_article","abstract":[{"lang":"eng","text":"This paper studies applications of envelopes of piecewise linear functions to problems in computational geometry. Among these applications we find problems involving hidden line/surface elimination, motion planning, transversals of polytopes, and a new type of Voronoi diagram for clusters of points. All results are either combinatorial or computational in nature. They are based on the combinatorial analysis in two companion papers [PS] and [E2] and a divide-and-conquer algorithm for computing envelopes described in this paper."}],"issue":"1"},{"type":"journal_article","issue":"1","abstract":[{"lang":"eng","text":"This paper investigates the combinatorial and computational aspects of certain extremal geometric problems in two and three dimensions. Specifically, we examine the problem of intersecting a convex subdivision with a line in order to maximize the number of intersections. A similar problem is to maximize the number of intersected facets in a cross-section of a three-dimensional convex polytope. Related problems concern maximum chains in certain families of posets defined over the regions of a convex subdivision. In most cases we are able to prove sharp bounds on the asymptotic behavior of the corresponding extremal functions. We also describe polynomial algorithms for all the problems discussed."}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4093","intvolume":" 4","title":"The complexity of cutting complexes","status":"public","oa_version":"None","article_processing_charge":"No","day":"01","citation":{"chicago":"Chazelle, Bernard, Herbert Edelsbrunner, and Leonidas Guibas. “The Complexity of Cutting Complexes.” Discrete & Computational Geometry. Springer, 1989. https://doi.org/10.1007/BF02187720.","mla":"Chazelle, Bernard, et al. “The Complexity of Cutting Complexes.” Discrete & Computational Geometry, vol. 4, no. 1, Springer, 1989, pp. 139–81, doi:10.1007/BF02187720.","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, Discrete & Computational Geometry 4 (1989) 139–181.","ista":"Chazelle B, Edelsbrunner H, Guibas L. 1989. The complexity of cutting complexes. Discrete & Computational Geometry. 4(1), 139–181.","ieee":"B. Chazelle, H. Edelsbrunner, and L. Guibas, “The complexity of cutting complexes,” Discrete & Computational Geometry, vol. 4, no. 1. Springer, pp. 139–181, 1989.","apa":"Chazelle, B., Edelsbrunner, H., & Guibas, L. (1989). The complexity of cutting complexes. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187720","ama":"Chazelle B, Edelsbrunner H, Guibas L. The complexity of cutting complexes. Discrete & Computational Geometry. 1989;4(1):139-181. doi:10.1007/BF02187720"},"publication":"Discrete & Computational Geometry","page":"139 - 181","date_published":"1989-03-01T00:00:00Z","publist_id":"2032","extern":"1","acknowledgement":"Bernard Chazelle wishes to acknowledge the National Science Foundation for supporting this research in part under Grant No. MCS83-03925. Herbert Edelsbrunner is pleased to acknowledge the support of Amoco Fnd. Fac. Dev. Comput. Sci. 1-6-44862. We wish to thank J. Pach and E. Szemeredi for valuable discussions on several\r\nof the problems studied in this paper.","year":"1989","publisher":"Springer","publication_status":"published","author":[{"first_name":"Bernard","last_name":"Chazelle","full_name":"Chazelle, Bernard"},{"last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"}],"volume":4,"date_created":"2018-12-11T12:06:54Z","date_updated":"2022-02-10T10:25:57Z","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"month":"03","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187720"}],"quality_controlled":"1","doi":"10.1007/BF02187720","language":[{"iso":"eng"}]},{"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"month":"01","doi":"10.1007/BF02187875","language":[{"iso":"eng"}],"quality_controlled":"1","publist_id":"2022","extern":"1","author":[{"last_name":"Chazelle","first_name":"Bernard","full_name":"Chazelle, Bernard"},{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"}],"volume":2,"date_updated":"2022-02-03T11:07:26Z","date_created":"2018-12-11T12:06:56Z","acknowledgement":"This research was conducted while the first author was with Brown University and the second author was with the Technical University of Graz, Austria. The first author was supported in part by NSF Grant MCS 83-03925.","year":"1987","publisher":"Springer","publication_status":"published","article_processing_charge":"No","day":"01","scopus_import":"1","date_published":"1987-01-01T00:00:00Z","citation":{"ama":"Chazelle B, Edelsbrunner H. Linear space data structures for two types of range search. Discrete & Computational Geometry. 1987;2(1):113-126. doi:10.1007/BF02187875","ista":"Chazelle B, Edelsbrunner H. 1987. Linear space data structures for two types of range search. Discrete & Computational Geometry. 2(1), 113–126.","apa":"Chazelle, B., & Edelsbrunner, H. (1987). Linear space data structures for two types of range search. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187875","ieee":"B. Chazelle and H. Edelsbrunner, “Linear space data structures for two types of range search,” Discrete & Computational Geometry, vol. 2, no. 1. Springer, pp. 113–126, 1987.","mla":"Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures for Two Types of Range Search.” Discrete & Computational Geometry, vol. 2, no. 1, Springer, 1987, pp. 113–26, doi:10.1007/BF02187875.","short":"B. Chazelle, H. Edelsbrunner, Discrete & Computational Geometry 2 (1987) 113–126.","chicago":"Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures for Two Types of Range Search.” Discrete & Computational Geometry. Springer, 1987. https://doi.org/10.1007/BF02187875."},"publication":"Discrete & Computational Geometry","page":"113 - 126","article_type":"original","issue":"1","abstract":[{"text":"This paper investigates the existence of linear space data structures for range searching. We examine thehomothetic range search problem, where a setS ofn points in the plane is to be preprocessed so that for any triangleT with sides parallel to three fixed directions the points ofS that lie inT can be computed efficiently. We also look atdomination searching in three dimensions. In this problem,S is a set ofn points inE 3 and the question is to retrieve all points ofS that are dominated by some query point. We describe linear space data structures for both problems. The query time is optimal in the first case and nearly optimal in the second.\r\n","lang":"eng"}],"type":"journal_article","oa_version":"None","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4100","intvolume":" 2","title":"Linear space data structures for two types of range search","status":"public"},{"day":"01","article_processing_charge":"No","date_published":"1986-01-01T00:00:00Z","publication":"Discrete & Computational Geometry","citation":{"ista":"Edelsbrunner H, Seidel R. 1986. Voronoi diagrams and arrangements. Discrete & Computational Geometry. 1(1), 25–44.","ieee":"H. Edelsbrunner and R. Seidel, “Voronoi diagrams and arrangements,” Discrete & Computational Geometry, vol. 1, no. 1. Springer, pp. 25–44, 1986.","apa":"Edelsbrunner, H., & Seidel, R. (1986). Voronoi diagrams and arrangements. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/BF02187681","ama":"Edelsbrunner H, Seidel R. Voronoi diagrams and arrangements. Discrete & Computational Geometry. 1986;1(1):25-44. doi:10.1007/BF02187681","chicago":"Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.” Discrete & Computational Geometry. Springer, 1986. https://doi.org/10.1007/BF02187681.","mla":"Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.” Discrete & Computational Geometry, vol. 1, no. 1, Springer, 1986, pp. 25–44, doi:10.1007/BF02187681.","short":"H. Edelsbrunner, R. Seidel, Discrete & Computational Geometry 1 (1986) 25–44."},"article_type":"original","page":"25 - 44","abstract":[{"text":"We propose a uniform and general framework for defining and dealing with Voronoi diagrams. In this framework a Voronoi diagram is a partition of a domainD induced by a finite number of real valued functions onD. Valuable insight can be gained when one considers how these real valued functions partitionD ×R. With this view it turns out that the standard Euclidean Voronoi diagram of point sets inR d along with its order-k generalizations are intimately related to certain arrangements of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms. We also discuss how the formalism of arrangements can be used to solve certain intersection and union problems.","lang":"eng"}],"issue":"1","type":"journal_article","oa_version":"None","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","_id":"4108","title":"Voronoi diagrams and arrangements","status":"public","intvolume":" 1","month":"01","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"doi":"10.1007/BF02187681","language":[{"iso":"eng"}],"quality_controlled":"1","publist_id":"2012","extern":"1","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert"},{"full_name":"Seidel, Raimund","last_name":"Seidel","first_name":"Raimund"}],"date_created":"2018-12-11T12:06:59Z","date_updated":"2022-02-01T08:53:39Z","volume":1,"year":"1986","acknowledgement":"We would like to thank John Gilbert for his careful reading of the manuscript and his many suggestions for improvement. We also want to thank Bennett Battaile, Gianfranco Bilardi, Joseph O'Rourke, and Chee Yap for their comments. ","publication_status":"published","publisher":"Springer"}]