[{"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"author":[{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"},{"first_name":"Georg F","full_name":"Osang, Georg F","last_name":"Osang","orcid":"0000-0002-8882-5116","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","oa_version":"Published Version","related_material":{"record":[{"relation":"earlier_version","id":"187","status":"public"}]},"publication":"Discrete and Computational Geometry","corr_author":"1","date_updated":"2025-06-12T06:36:54Z","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).","date_published":"2021-03-31T00:00:00Z","file_date_updated":"2021-12-01T10:56:53Z","day":"31","isi":1,"type":"journal_article","page":"1296–1313","department":[{"_id":"HeEd"}],"publication_status":"published","intvolume":"        65","file":[{"success":1,"date_created":"2021-12-01T10:56:53Z","relation":"main_file","date_updated":"2021-12-01T10:56:53Z","file_size":677704,"access_level":"open_access","file_name":"2021_DisCompGeo_Edelsbrunner_Osang.pdf","content_type":"application/pdf","file_id":"10394","creator":"cchlebak","checksum":"59b4e1e827e494209bcb4aae22e1d347"}],"publisher":"Springer Nature","title":"The multi-cover persistence of Euclidean balls","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"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."}],"pmid":1,"scopus_import":"1","has_accepted_license":"1","year":"2021","ec_funded":1,"ddc":["516"],"_id":"9317","quality_controlled":"1","article_processing_charge":"Yes (via OA deal)","oa":1,"external_id":{"isi":["000635460400001"],"pmid":["34720303"]},"project":[{"_id":"266A2E9E-B435-11E9-9278-68D0E5697425","call_identifier":"H2020","grant_number":"788183","name":"Alpha Shape Theory Extended"},{"name":"Persistence and stability of geometric complexes","_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"I02979-N35"}],"date_created":"2021-04-11T22:01:15Z","status":"public","citation":{"ama":"Edelsbrunner H, Osang GF. The multi-cover persistence of Euclidean balls. <i>Discrete and Computational Geometry</i>. 2021;65:1296–1313. doi:<a href=\"https://doi.org/10.1007/s00454-021-00281-9\">10.1007/s00454-021-00281-9</a>","ieee":"H. Edelsbrunner and G. F. Osang, “The multi-cover persistence of Euclidean balls,” <i>Discrete and Computational Geometry</i>, vol. 65. Springer Nature, pp. 1296–1313, 2021.","mla":"Edelsbrunner, Herbert, and Georg F. Osang. “The Multi-Cover Persistence of Euclidean Balls.” <i>Discrete and Computational Geometry</i>, vol. 65, Springer Nature, 2021, pp. 1296–1313, doi:<a href=\"https://doi.org/10.1007/s00454-021-00281-9\">10.1007/s00454-021-00281-9</a>.","apa":"Edelsbrunner, H., &#38; Osang, G. F. (2021). The multi-cover persistence of Euclidean balls. <i>Discrete and Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-021-00281-9\">https://doi.org/10.1007/s00454-021-00281-9</a>","short":"H. Edelsbrunner, G.F. Osang, Discrete and Computational Geometry 65 (2021) 1296–1313.","chicago":"Edelsbrunner, Herbert, and Georg F Osang. “The Multi-Cover Persistence of Euclidean Balls.” <i>Discrete and Computational Geometry</i>. Springer Nature, 2021. <a href=\"https://doi.org/10.1007/s00454-021-00281-9\">https://doi.org/10.1007/s00454-021-00281-9</a>.","ista":"Edelsbrunner H, Osang GF. 2021. The multi-cover persistence of Euclidean balls. Discrete and Computational Geometry. 65, 1296–1313."},"month":"03","language":[{"iso":"eng"}],"volume":65,"doi":"10.1007/s00454-021-00281-9"},{"corr_author":"1","date_updated":"2026-04-08T07:23:01Z","related_material":{"record":[{"relation":"earlier_version","id":"683","status":"public"},{"relation":"dissertation_contains","status":"public","id":"7944"}]},"publication":"Discrete & Computational Geometry","article_type":"original","arxiv":1,"oa_version":"Published Version","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"author":[{"first_name":"Anna","full_name":"Lubiw, Anna","last_name":"Lubiw"},{"id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","last_name":"Masárová","full_name":"Masárová, Zuzana","first_name":"Zuzana"},{"first_name":"Uli","full_name":"Wagner, Uli","last_name":"Wagner","orcid":"0000-0002-1494-0568","id":"36690CA2-F248-11E8-B48F-1D18A9856A87"}],"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","publication_status":"published","file":[{"date_created":"2019-02-14T11:57:22Z","relation":"main_file","date_updated":"2020-07-14T12:47:14Z","file_size":556276,"access_level":"open_access","file_name":"2018_DiscreteGeometry_Lubiw.pdf","checksum":"e1bff88f1d77001b53b78c485ce048d7","creator":"dernst","file_id":"5988","content_type":"application/pdf"}],"intvolume":"        61","day":"01","file_date_updated":"2020-07-14T12:47:14Z","department":[{"_id":"UlWa"}],"type":"journal_article","isi":1,"page":"880-898","date_published":"2019-06-01T00:00:00Z","year":"2019","has_accepted_license":"1","scopus_import":"1","abstract":[{"lang":"eng","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."}],"publisher":"Springer Nature","title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"volume":61,"language":[{"iso":"eng"}],"doi":"10.1007/s00454-018-0035-8","status":"public","date_created":"2019-02-14T11:54:08Z","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"month":"06","issue":"4","citation":{"ista":"Lubiw A, Masárová Z, Wagner U. 2019. A proof of the orbit conjecture for flipping edge-labelled triangulations. Discrete &#38; Computational Geometry. 61(4), 880–898.","chicago":"Lubiw, Anna, Zuzana Masárová, and Uli Wagner. “A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2019. <a href=\"https://doi.org/10.1007/s00454-018-0035-8\">https://doi.org/10.1007/s00454-018-0035-8</a>.","short":"A. Lubiw, Z. Masárová, U. Wagner, Discrete &#38; Computational Geometry 61 (2019) 880–898.","apa":"Lubiw, A., Masárová, Z., &#38; Wagner, U. (2019). A proof of the orbit conjecture for flipping edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-018-0035-8\">https://doi.org/10.1007/s00454-018-0035-8</a>","ama":"Lubiw A, Masárová Z, Wagner U. A proof of the orbit conjecture for flipping edge-labelled triangulations. <i>Discrete &#38; Computational Geometry</i>. 2019;61(4):880-898. doi:<a href=\"https://doi.org/10.1007/s00454-018-0035-8\">10.1007/s00454-018-0035-8</a>","ieee":"A. Lubiw, Z. Masárová, and U. Wagner, “A proof of the orbit conjecture for flipping edge-labelled triangulations,” <i>Discrete &#38; Computational Geometry</i>, 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.” <i>Discrete &#38; Computational Geometry</i>, vol. 61, no. 4, Springer Nature, 2019, pp. 880–98, doi:<a href=\"https://doi.org/10.1007/s00454-018-0035-8\">10.1007/s00454-018-0035-8</a>."},"oa":1,"external_id":{"isi":["000466130000009"],"arxiv":["1710.02741"]},"ddc":["000"],"_id":"5986","quality_controlled":"1","article_processing_charge":"Yes (via OA deal)"},{"publication_status":"published","file":[{"file_size":482518,"access_level":"open_access","file_name":"2018_DiscreteComp_Akopyan.pdf","creator":"dernst","content_type":"application/pdf","file_id":"5844","success":1,"date_created":"2019-01-18T09:27:36Z","relation":"main_file","date_updated":"2019-01-18T09:27:36Z"}],"intvolume":"        59","date_published":"2018-06-01T00:00:00Z","file_date_updated":"2019-01-18T09:27:36Z","day":"01","department":[{"_id":"HeEd"}],"type":"journal_article","isi":1,"page":"1001-1009","publication":"Discrete & Computational Geometry","corr_author":"1","date_updated":"2026-05-20T10:19:33Z","author":[{"first_name":"Arseniy","full_name":"Akopyan, Arseniy","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","last_name":"Akopyan","orcid":"0000-0002-2548-617X"},{"last_name":"Balitskiy","full_name":"Balitskiy, Alexey","first_name":"Alexey"},{"full_name":"Grigorev, Mikhail","first_name":"Mikhail","last_name":"Grigorev"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publist_id":"6324","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","oa_version":"Published Version","status":"public","project":[{"name":"International IST Postdoc Fellowship Programme","grant_number":"291734","call_identifier":"FP7","_id":"25681D80-B435-11E9-9278-68D0E5697425"}],"date_created":"2018-12-11T11:49:57Z","month":"06","issue":"4","citation":{"apa":"Akopyan, A., Balitskiy, A., &#38; Grigorev, M. (2018). On the circle covering theorem by A.W. Goodman and R.E. Goodman. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-017-9883-x\">https://doi.org/10.1007/s00454-017-9883-x</a>","ieee":"A. Akopyan, A. Balitskiy, and M. Grigorev, “On the circle covering theorem by A.W. Goodman and R.E. Goodman,” <i>Discrete &#38; Computational Geometry</i>, vol. 59, no. 4. Springer, pp. 1001–1009, 2018.","mla":"Akopyan, Arseniy, et al. “On the Circle Covering Theorem by A.W. Goodman and R.E. Goodman.” <i>Discrete &#38; Computational Geometry</i>, vol. 59, no. 4, Springer, 2018, pp. 1001–09, doi:<a href=\"https://doi.org/10.1007/s00454-017-9883-x\">10.1007/s00454-017-9883-x</a>.","ama":"Akopyan A, Balitskiy A, Grigorev M. On the circle covering theorem by A.W. Goodman and R.E. Goodman. <i>Discrete &#38; Computational Geometry</i>. 2018;59(4):1001-1009. doi:<a href=\"https://doi.org/10.1007/s00454-017-9883-x\">10.1007/s00454-017-9883-x</a>","chicago":"Akopyan, Arseniy, Alexey Balitskiy, and Mikhail Grigorev. “On the Circle Covering Theorem by A.W. Goodman and R.E. Goodman.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2018. <a href=\"https://doi.org/10.1007/s00454-017-9883-x\">https://doi.org/10.1007/s00454-017-9883-x</a>.","ista":"Akopyan A, Balitskiy A, Grigorev M. 2018. On the circle covering theorem by A.W. Goodman and R.E. Goodman. Discrete &#38; Computational Geometry. 59(4), 1001–1009.","short":"A. Akopyan, A. Balitskiy, M. Grigorev, Discrete &#38; Computational Geometry 59 (2018) 1001–1009."},"volume":59,"language":[{"iso":"eng"}],"doi":"10.1007/s00454-017-9883-x","ddc":["516","000"],"quality_controlled":"1","_id":"1064","article_processing_charge":"Yes (via OA deal)","oa":1,"external_id":{"isi":["000432205500011"]},"has_accepted_license":"1","year":"2018","ec_funded":1,"scopus_import":"1","publisher":"Springer","tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)"},"title":"On the circle covering theorem by A.W. Goodman and R.E. Goodman","abstract":[{"lang":"eng","text":"In 1945, A.W. Goodman and R.E. Goodman proved the following conjecture by P. Erdős: Given a family of (round) disks of radii r1, … , rn in the plane, it is always possible to cover them by a disk of radius R= ∑ ri, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body K⊂ Rd with homothety coefficients τ1, … , τn> 0 , it is always possible to cover them by a translate of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets."}]},{"external_id":{"arxiv":["1512.08762"]},"OA_type":"green","article_processing_charge":"No","_id":"22198","quality_controlled":"1","doi":"10.1007/s00454-016-9843-x","OA_place":"repository","language":[{"iso":"eng"}],"volume":58,"citation":{"apa":"Connelly, R., Funkhouser, M., Kuperberg, V. Z., &#38; Solomonides, E. (2017). Packings of equal disks in a square torus. <i>Discrete &#38; Computational Geometry</i>. Springer Nature. <a href=\"https://doi.org/10.1007/s00454-016-9843-x\">https://doi.org/10.1007/s00454-016-9843-x</a>","ama":"Connelly R, Funkhouser M, Kuperberg VZ, Solomonides E. Packings of equal disks in a square torus. <i>Discrete &#38; Computational Geometry</i>. 2017;58(3):614-642. doi:<a href=\"https://doi.org/10.1007/s00454-016-9843-x\">10.1007/s00454-016-9843-x</a>","ieee":"R. Connelly, M. Funkhouser, V. Z. Kuperberg, and E. Solomonides, “Packings of equal disks in a square torus,” <i>Discrete &#38; Computational Geometry</i>, vol. 58, no. 3. Springer Nature, pp. 614–642, 2017.","mla":"Connelly, Robert, et al. “Packings of Equal Disks in a Square Torus.” <i>Discrete &#38; Computational Geometry</i>, vol. 58, no. 3, Springer Nature, 2017, pp. 614–42, doi:<a href=\"https://doi.org/10.1007/s00454-016-9843-x\">10.1007/s00454-016-9843-x</a>.","chicago":"Connelly, Robert, Matthew Funkhouser, Vivian Zieve Kuperberg, and Evan Solomonides. “Packings of Equal Disks in a Square Torus.” <i>Discrete &#38; Computational Geometry</i>. Springer Nature, 2017. <a href=\"https://doi.org/10.1007/s00454-016-9843-x\">https://doi.org/10.1007/s00454-016-9843-x</a>.","ista":"Connelly R, Funkhouser M, Kuperberg VZ, Solomonides E. 2017. Packings of equal disks in a square torus. Discrete &#38; Computational Geometry. 58(3), 614–642.","short":"R. Connelly, M. Funkhouser, V.Z. Kuperberg, E. Solomonides, Discrete &#38; Computational Geometry 58 (2017) 614–642."},"issue":"3","month":"01","date_created":"2026-06-29T12:58:50Z","status":"public","abstract":[{"lang":"eng","text":"Packings of equal disks in the plane are known to have density at most\r\nπ/\r\n√\r\n12, although this density is never achieved in the square torus, which is what we\r\ncall the plane modulo the square lattice. We find packings of disks in a square torus\r\nthat we conjecture to be the most dense for certain numbers of packing disks, using\r\ncontinued fractions to approximate 1/\r\n√\r\n3 and 2 −\r\n√\r\n3. We also define a constant to\r\nmeasure the efficiency of a packing motived by a related constant due to Markov for\r\ncontinued fractions. One idea is to use the unique factorization property of Gaussian\r\nintegers to prove that there is an upper bound for the Markov constant for grid-like\r\npackings. By way of contrast, we show that an upper bound by Gruber [In many cases\r\noptimal configurations are almost regular hexagonal, vol. 65, pp. 121–145, 1999;Geom\r\nDedicata 84(1–3):271–320, 2001] for the error for the limiting density of a packing\r\nof equal disks in a planar square, which is on the order of 1/\r\n√\r\nN, is the best possible,\r\nwhereas for our examples for the square torus, the error for the limiting density is on\r\nthe order of 1/N, where N is the number of packing disks."}],"title":"Packings of equal disks in a square torus","publisher":"Springer Nature","scopus_import":"1","year":"2017","extern":"1","type":"journal_article","page":"614-642","day":"09","date_published":"2017-01-09T00:00:00Z","intvolume":"        58","publication_status":"published","oa_version":"Preprint","main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1512.08762"}],"arxiv":1,"article_type":"original","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Robert","full_name":"Connelly, Robert","last_name":"Connelly"},{"full_name":"Funkhouser, Matthew","first_name":"Matthew","last_name":"Funkhouser"},{"full_name":"Kuperberg, Vivian Zieve","first_name":"Vivian Zieve","id":"c3bac823-112d-11f0-a3f5-c264f852e697","last_name":"Kuperberg"},{"last_name":"Solomonides","full_name":"Solomonides, Evan","first_name":"Evan"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"date_updated":"2026-07-14T11:14:51Z","publication":"Discrete & Computational Geometry"},{"month":"06","citation":{"short":"H. Edelsbrunner, B.T. Fasy, G. Rote, Discrete &#38; Computational Geometry 49 (2013) 797–822.","ista":"Edelsbrunner H, Fasy BT, Rote G. 2013. Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions. Discrete &#38; Computational Geometry. 49(4), 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.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2013. <a href=\"https://doi.org/10.1007/s00454-013-9517-x\">https://doi.org/10.1007/s00454-013-9517-x</a>.","ama":"Edelsbrunner H, Fasy BT, Rote G. Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions. <i>Discrete &#38; Computational Geometry</i>. 2013;49(4):797-822. doi:<a href=\"https://doi.org/10.1007/s00454-013-9517-x\">10.1007/s00454-013-9517-x</a>","mla":"Edelsbrunner, Herbert, et al. “Add Isotropic Gaussian Kernels at Own Risk: More and More Resilient Modes in Higher Dimensions.” <i>Discrete &#38; Computational Geometry</i>, vol. 49, no. 4, Springer, 2013, pp. 797–822, doi:<a href=\"https://doi.org/10.1007/s00454-013-9517-x\">10.1007/s00454-013-9517-x</a>.","ieee":"H. Edelsbrunner, B. T. Fasy, and G. Rote, “Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions,” <i>Discrete &#38; Computational Geometry</i>, vol. 49, no. 4. Springer, pp. 797–822, 2013.","apa":"Edelsbrunner, H., Fasy, B. T., &#38; Rote, G. (2013). Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-013-9517-x\">https://doi.org/10.1007/s00454-013-9517-x</a>"},"issue":"4","status":"public","date_created":"2018-12-11T11:59:44Z","doi":"10.1007/s00454-013-9517-x","volume":49,"language":[{"iso":"eng"}],"_id":"2815","article_processing_charge":"No","quality_controlled":"1","ddc":["500"],"external_id":{"isi":["000320672400005"]},"oa":1,"year":"2013","scopus_import":"1","title":"Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions","publisher":"Springer","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."}],"intvolume":"        49","publication_status":"published","date_published":"2013-06-01T00:00:00Z","department":[{"_id":"HeEd"}],"page":"797 - 822","isi":1,"type":"journal_article","day":"01","publication":"Discrete & Computational Geometry","related_material":{"record":[{"relation":"earlier_version","id":"3134","status":"public"}]},"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.","date_updated":"2026-06-18T18:35:33Z","corr_author":"1","publist_id":"3991","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","author":[{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner"},{"full_name":"Fasy, Brittany Terese","first_name":"Brittany Terese","id":"F65D502E-E68D-11E9-9252-C644099818F6","last_name":"Fasy"},{"first_name":"Günter","full_name":"Rote, Günter","last_name":"Rote"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"main_file_link":[{"url":"https://doi.org/10.1007/s00454-013-9517-x","open_access":"1"}],"oa_version":"Published Version","article_type":"original"},{"article_type":"original","abstract":[{"lang":"eng","text":"We present algorithms for constructing a hierarchy of increasingly coarse Morse-Smale complexes that decompose a piecewise linear 2-manifold. While these complexes are defined only in the smooth category, we extend the construction to the piecewise linearcategory by ensuring structural integrity and simulating differentiability. We then simplify Morse-Smale complexes by canceling pairs of critical points in order of increasing persistence."}],"oa_version":"None","publisher":"Springer nature","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"last_name":"Harer","first_name":"John","full_name":"Harer, John"},{"last_name":"Zomorodian","first_name":"Afra","full_name":"Zomorodian, Afra"}],"publication_identifier":{"eissn":["1432-0444"],"issnl":["0179-5376"]},"publist_id":"2134","user_id":"ba8df636-2132-11f1-aed0-ed93e2281fdd","title":"Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds","extern":"1","year":"2003","date_updated":"2026-05-06T08:08:23Z","publication":"Discrete & Computational Geometry","day":"01","OA_type":"closed access","type":"journal_article","page":"87 - 107","_id":"3993","article_processing_charge":"No","date_published":"2003-05-01T00:00:00Z","quality_controlled":"1","volume":30,"language":[{"iso":"eng"}],"doi":"10.1007/s00454-003-2926-5","status":"public","publication_status":"published","date_created":"2018-12-11T12:06:19Z","month":"05","citation":{"mla":"Edelsbrunner, Herbert, et al. “Hierarchical Morse-Smale Complexes for Piecewise Linear 2-Manifolds.” <i>Discrete &#38; Computational Geometry</i>, vol. 30, Springer nature, 2003, pp. 87–107, doi:<a href=\"https://doi.org/10.1007/s00454-003-2926-5\">10.1007/s00454-003-2926-5</a>.","ieee":"H. Edelsbrunner, J. Harer, and A. Zomorodian, “Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds,” <i>Discrete &#38; Computational Geometry</i>, vol. 30. Springer nature, pp. 87–107, 2003.","ama":"Edelsbrunner H, Harer J, Zomorodian A. Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. <i>Discrete &#38; Computational Geometry</i>. 2003;30:87-107. doi:<a href=\"https://doi.org/10.1007/s00454-003-2926-5\">10.1007/s00454-003-2926-5</a>","apa":"Edelsbrunner, H., Harer, J., &#38; Zomorodian, A. (2003). Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. <i>Discrete &#38; Computational Geometry</i>. Springer nature. <a href=\"https://doi.org/10.1007/s00454-003-2926-5\">https://doi.org/10.1007/s00454-003-2926-5</a>","short":"H. Edelsbrunner, J. Harer, A. Zomorodian, Discrete &#38; Computational Geometry 30 (2003) 87–107.","ista":"Edelsbrunner H, Harer J, Zomorodian A. 2003. Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds. Discrete &#38; Computational Geometry. 30, 87–107.","chicago":"Edelsbrunner, Herbert, John Harer, and Afra Zomorodian. “Hierarchical Morse-Smale Complexes for Piecewise Linear 2-Manifolds.” <i>Discrete &#38; Computational Geometry</i>. Springer nature, 2003. <a href=\"https://doi.org/10.1007/s00454-003-2926-5\">https://doi.org/10.1007/s00454-003-2926-5</a>."},"intvolume":"        30"},{"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}&gt;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}."}],"title":"Euclidean minimum spanning trees and bichromatic closest pairs","publisher":"Springer","scopus_import":"1","year":"1991","extern":"1","oa":1,"_id":"4061","quality_controlled":"1","article_processing_charge":"No","doi":"10.1007/BF02574698","language":[{"iso":"eng"}],"volume":6,"citation":{"ama":"Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. Euclidean minimum spanning trees and bichromatic closest pairs. <i>Discrete &#38; Computational Geometry</i>. 1991;6(1):407-422. doi:<a href=\"https://doi.org/10.1007/BF02574698\">10.1007/BF02574698</a>","mla":"Agarwal, Pankaj, et al. “Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1, Springer, 1991, pp. 407–22, doi:<a href=\"https://doi.org/10.1007/BF02574698\">10.1007/BF02574698</a>.","ieee":"P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, and E. Welzl, “Euclidean minimum spanning trees and bichromatic closest pairs,” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1. Springer, pp. 407–422, 1991.","apa":"Agarwal, P., Edelsbrunner, H., Schwarzkopf, O., &#38; Welzl, E. (1991). Euclidean minimum spanning trees and bichromatic closest pairs. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02574698\">https://doi.org/10.1007/BF02574698</a>","short":"P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, Discrete &#38; Computational Geometry 6 (1991) 407–422.","ista":"Agarwal P, Edelsbrunner H, Schwarzkopf O, Welzl E. 1991. Euclidean minimum spanning trees and bichromatic closest pairs. Discrete &#38; Computational Geometry. 6(1), 407–422.","chicago":"Agarwal, Pankaj, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. “Euclidean Minimum Spanning Trees and Bichromatic Closest Pairs.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1991. <a href=\"https://doi.org/10.1007/BF02574698\">https://doi.org/10.1007/BF02574698</a>."},"issue":"1","month":"12","date_created":"2018-12-11T12:06:42Z","status":"public","oa_version":"Published Version","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02574698","open_access":"1"}],"article_type":"original","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publist_id":"2062","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"author":[{"full_name":"Agarwal, Pankaj","first_name":"Pankaj","last_name":"Agarwal"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"first_name":"Otfried","full_name":"Schwarzkopf, Otfried","last_name":"Schwarzkopf"},{"first_name":"Emo","full_name":"Welzl, Emo","last_name":"Welzl"}],"date_updated":"2022-02-24T15:06:41Z","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).","publication":"Discrete & Computational Geometry","type":"journal_article","page":"407 - 422","day":"01","date_published":"1991-12-01T00:00:00Z","intvolume":"         6","publication_status":"published"},{"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"author":[{"first_name":"Boris","full_name":"Aronov, Boris","last_name":"Aronov"},{"last_name":"Chazelle","full_name":"Chazelle, Bernard","first_name":"Bernard"},{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner"},{"last_name":"Guibas","first_name":"Leonidas","full_name":"Guibas, Leonidas"},{"last_name":"Sharir","first_name":"Micha","full_name":"Sharir, Micha"},{"last_name":"Wenger","full_name":"Wenger, Rephael","first_name":"Rephael"}],"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publist_id":"2063","article_type":"original","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02574700","open_access":"1"}],"oa_version":"Published Version","publication":"Discrete & Computational Geometry","date_updated":"2022-02-24T15:39:25Z","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","date_published":"1991-12-01T00:00:00Z","day":"01","type":"journal_article","page":"435 - 442","publication_status":"published","intvolume":"         6","publisher":"Springer","title":"Points and triangles in the plane and halving planes in space","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"}],"extern":"1","scopus_import":"1","year":"1991","quality_controlled":"1","_id":"4062","article_processing_charge":"No","oa":1,"date_created":"2018-12-11T12:06:43Z","status":"public","issue":"1","citation":{"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.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1991. <a href=\"https://doi.org/10.1007/BF02574700\">https://doi.org/10.1007/BF02574700</a>.","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 &#38; Computational Geometry. 6(1), 435–442.","short":"B. Aronov, B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, R. Wenger, Discrete &#38; Computational Geometry 6 (1991) 435–442.","apa":"Aronov, B., Chazelle, B., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Wenger, R. (1991). Points and triangles in the plane and halving planes in space. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02574700\">https://doi.org/10.1007/BF02574700</a>","ama":"Aronov B, Chazelle B, Edelsbrunner H, Guibas L, Sharir M, Wenger R. Points and triangles in the plane and halving planes in space. <i>Discrete &#38; Computational Geometry</i>. 1991;6(1):435-442. doi:<a href=\"https://doi.org/10.1007/BF02574700\">10.1007/BF02574700</a>","mla":"Aronov, Boris, et al. “Points and Triangles in the Plane and Halving Planes in Space.” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1, Springer, 1991, pp. 435–42, doi:<a href=\"https://doi.org/10.1007/BF02574700\">10.1007/BF02574700</a>.","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,” <i>Discrete &#38; Computational Geometry</i>, vol. 6, no. 1. Springer, pp. 435–442, 1991."},"month":"12","language":[{"iso":"eng"}],"volume":6,"doi":"10.1007/BF02574700"},{"scopus_import":"1","year":"1990","extern":"1","title":"The complexity of many cells in arrangements of planes and related problems","publisher":"Springer","abstract":[{"lang":"eng","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&gt;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&gt;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&gt;0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d&gt;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."}],"citation":{"short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 5 (1990) 197–216.","ista":"Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity of many cells in arrangements of planes and related problems. Discrete &#38; Computational Geometry. 5(1), 197–216.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity of Many Cells in Arrangements of Planes and Related Problems.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187785\">https://doi.org/10.1007/BF02187785</a>.","mla":"Edelsbrunner, Herbert, et al. “The Complexity of Many Cells in Arrangements of Planes and Related Problems.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 197–216, doi:<a href=\"https://doi.org/10.1007/BF02187785\">10.1007/BF02187785</a>.","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity of many cells in arrangements of planes and related problems,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 197–216, 1990.","ama":"Edelsbrunner H, Guibas L, Sharir M. The complexity of many cells in arrangements of planes and related problems. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):197-216. doi:<a href=\"https://doi.org/10.1007/BF02187785\">10.1007/BF02187785</a>","apa":"Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1990). The complexity of many cells in arrangements of planes and related problems. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187785\">https://doi.org/10.1007/BF02187785</a>"},"issue":"1","month":"03","date_created":"2018-12-11T12:06:44Z","status":"public","doi":"10.1007/BF02187785","language":[{"iso":"eng"}],"volume":5,"_id":"4066","article_processing_charge":"No","quality_controlled":"1","publication":"Discrete & Computational Geometry","date_updated":"2022-02-22T11:02:41Z","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","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publist_id":"2054","author":[{"last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"first_name":"Leonidas","full_name":"Guibas, Leonidas","last_name":"Guibas"},{"first_name":"Micha","full_name":"Sharir, Micha","last_name":"Sharir"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187785"}],"oa_version":"None","article_type":"original","intvolume":"         5","publication_status":"published","date_published":"1990-03-01T00:00:00Z","page":"197 - 216","type":"journal_article","day":"01"},{"date_published":"1990-01-01T00:00:00Z","type":"journal_article","page":"35 - 42","day":"01","intvolume":"         5","publication_status":"published","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publist_id":"2057","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"author":[{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Sharir","first_name":"Micha","full_name":"Sharir, Micha"}],"oa_version":"None","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187778"}],"article_type":"original","publication":"Discrete & Computational Geometry","date_updated":"2022-02-22T14:50:34Z","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.","quality_controlled":"1","_id":"4068","article_processing_charge":"No","citation":{"mla":"Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 35–42, doi:<a href=\"https://doi.org/10.1007/BF02187778\">10.1007/BF02187778</a>.","ieee":"H. Edelsbrunner and M. Sharir, “The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 35–42, 1990.","ama":"Edelsbrunner H, Sharir M. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):35-42. doi:<a href=\"https://doi.org/10.1007/BF02187778\">10.1007/BF02187778</a>","apa":"Edelsbrunner, H., &#38; Sharir, M. (1990). The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187778\">https://doi.org/10.1007/BF02187778</a>","short":"H. Edelsbrunner, M. Sharir, Discrete &#38; Computational Geometry 5 (1990) 35–42.","chicago":"Edelsbrunner, Herbert, and Micha Sharir. “The Maximum Number of Ways to Stabn Convex Nonintersecting Sets in the Plane Is 2n−2.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187778\">https://doi.org/10.1007/BF02187778</a>.","ista":"Edelsbrunner H, Sharir M. 1990. The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2. Discrete &#38; Computational Geometry. 5(1), 35–42."},"issue":"1","month":"01","date_created":"2018-12-11T12:06:45Z","status":"public","doi":"10.1007/BF02187778","language":[{"iso":"eng"}],"volume":5,"title":"The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2","publisher":"Springer","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."}],"year":"1990","extern":"1"},{"article_type":"original","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187784"}],"oa_version":"None","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"first_name":"Leonidas","full_name":"Guibas, Leonidas","last_name":"Guibas"},{"last_name":"Sharir","first_name":"Micha","full_name":"Sharir, Micha"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publist_id":"2053","date_updated":"2022-02-22T09:27:30Z","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.","publication":"Discrete & Computational Geometry","day":"01","page":"161 - 196","type":"journal_article","date_published":"1990-01-01T00:00:00Z","publication_status":"published","intvolume":"         5","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&gt;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&gt;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)."}],"publisher":"Springer","title":"The complexity and construction of many faces in arrangements of lines and of segments","extern":"1","scopus_import":"1","year":"1990","quality_controlled":"1","_id":"4072","article_processing_charge":"No","language":[{"iso":"eng"}],"volume":5,"doi":"10.1007/BF02187784","date_created":"2018-12-11T12:06:46Z","status":"public","citation":{"short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 5 (1990) 161–196.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187784\">https://doi.org/10.1007/BF02187784</a>.","ista":"Edelsbrunner H, Guibas L, Sharir M. 1990. The complexity and construction of many faces in arrangements of lines and of segments. Discrete &#38; 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. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):161-196. doi:<a href=\"https://doi.org/10.1007/BF02187784\">10.1007/BF02187784</a>","mla":"Edelsbrunner, Herbert, et al. “The Complexity and Construction of Many Faces in Arrangements of Lines and of Segments.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 161–96, doi:<a href=\"https://doi.org/10.1007/BF02187784\">10.1007/BF02187784</a>.","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The complexity and construction of many faces in arrangements of lines and of segments,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 161–196, 1990.","apa":"Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1990). The complexity and construction of many faces in arrangements of lines and of segments. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187784\">https://doi.org/10.1007/BF02187784</a>"},"issue":"1","month":"01"},{"abstract":[{"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.","lang":"eng"}],"publisher":"Springer","title":"Combinatorial complexity bounds for arrangements of curves and spheres","extern":"1","year":"1990","article_processing_charge":"No","_id":"4074","quality_controlled":"1","volume":5,"language":[{"iso":"eng"}],"doi":"10.1007/BF02187783","status":"public","date_created":"2018-12-11T12:06:47Z","month":"03","citation":{"chicago":"Clarkson, Kenneth, Herbert Edelsbrunner, Leonidas Guibas, Micha Sharir, and Emo Welzl. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1990. <a href=\"https://doi.org/10.1007/BF02187783\">https://doi.org/10.1007/BF02187783</a>.","ista":"Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. 1990. Combinatorial complexity bounds for arrangements of curves and spheres. Discrete &#38; Computational Geometry. 5(1), 99–160.","short":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, E. Welzl, Discrete &#38; Computational Geometry 5 (1990) 99–160.","apa":"Clarkson, K., Edelsbrunner, H., Guibas, L., Sharir, M., &#38; Welzl, E. (1990). Combinatorial complexity bounds for arrangements of curves and spheres. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187783\">https://doi.org/10.1007/BF02187783</a>","ama":"Clarkson K, Edelsbrunner H, Guibas L, Sharir M, Welzl E. Combinatorial complexity bounds for arrangements of curves and spheres. <i>Discrete &#38; Computational Geometry</i>. 1990;5(1):99-160. doi:<a href=\"https://doi.org/10.1007/BF02187783\">10.1007/BF02187783</a>","mla":"Clarkson, Kenneth, et al. “Combinatorial Complexity Bounds for Arrangements of Curves and Spheres.” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1, Springer, 1990, pp. 99–160, doi:<a href=\"https://doi.org/10.1007/BF02187783\">10.1007/BF02187783</a>.","ieee":"K. Clarkson, H. Edelsbrunner, L. Guibas, M. Sharir, and E. Welzl, “Combinatorial complexity bounds for arrangements of curves and spheres,” <i>Discrete &#38; Computational Geometry</i>, vol. 5, no. 1. Springer, pp. 99–160, 1990."},"issue":"1","article_type":"original","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187783"}],"oa_version":"None","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"author":[{"first_name":"Kenneth","full_name":"Clarkson, Kenneth","last_name":"Clarkson"},{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"},{"last_name":"Sharir","first_name":"Micha","full_name":"Sharir, Micha"},{"last_name":"Welzl","full_name":"Welzl, Emo","first_name":"Emo"}],"publist_id":"2048","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","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.","date_updated":"2022-02-17T15:41:04Z","publication":"Discrete & Computational Geometry","day":"01","type":"journal_article","page":"99 - 160","date_published":"1990-03-01T00:00:00Z","publication_status":"published","intvolume":"         5"},{"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.","date_updated":"2022-02-10T15:53:48Z","publication":"Discrete & Computational Geometry","oa_version":"Published Version","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187733","open_access":"1"}],"article_type":"original","publist_id":"2038","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","author":[{"first_name":"Herbert","full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner"},{"first_name":"Leonidas","full_name":"Guibas, Leonidas","last_name":"Guibas"},{"last_name":"Sharir","first_name":"Micha","full_name":"Sharir, Micha"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"intvolume":"         4","publication_status":"published","page":"311 - 336","type":"journal_article","day":"01","date_published":"1989-12-01T00:00:00Z","year":"1989","extern":"1","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."}],"title":"The upper envelope of piecewise linear functions: Algorithms and applications","publisher":"Springer","doi":"10.1007/BF02187733","volume":4,"language":[{"iso":"eng"}],"month":"12","issue":"1","citation":{"chicago":"Edelsbrunner, Herbert, Leonidas Guibas, and Micha Sharir. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187733\">https://doi.org/10.1007/BF02187733</a>.","ista":"Edelsbrunner H, Guibas L, Sharir M. 1989. The upper envelope of piecewise linear functions: Algorithms and applications. Discrete &#38; Computational Geometry. 4(1), 311–336.","short":"H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 4 (1989) 311–336.","apa":"Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1989). The upper envelope of piecewise linear functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187733\">https://doi.org/10.1007/BF02187733</a>","mla":"Edelsbrunner, Herbert, et al. “The Upper Envelope of Piecewise Linear Functions: Algorithms and Applications.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 311–36, doi:<a href=\"https://doi.org/10.1007/BF02187733\">10.1007/BF02187733</a>.","ieee":"H. Edelsbrunner, L. Guibas, and M. Sharir, “The upper envelope of piecewise linear functions: Algorithms and applications,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 311–336, 1989.","ama":"Edelsbrunner H, Guibas L, Sharir M. The upper envelope of piecewise linear functions: Algorithms and applications. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):311-336. doi:<a href=\"https://doi.org/10.1007/BF02187733\">10.1007/BF02187733</a>"},"status":"public","date_created":"2018-12-11T12:06:50Z","oa":1,"_id":"4081","quality_controlled":"1","article_processing_charge":"No"},{"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"}],"title":"The upper envelope of piecewise linear functions: Tight bounds on the number of faces ","publisher":"Springer","year":"1989","scopus_import":"1","extern":"1","oa":1,"quality_controlled":"1","_id":"4086","article_processing_charge":"No","doi":"10.1007/BF02187734","volume":4,"language":[{"iso":"eng"}],"month":"11","issue":"4","citation":{"apa":"Edelsbrunner, H. (1989). The upper envelope of piecewise linear functions: Tight bounds on the number of faces . <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187734\">https://doi.org/10.1007/BF02187734</a>","mla":"Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces .” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 4, Springer, 1989, pp. 337–43, doi:<a href=\"https://doi.org/10.1007/BF02187734\">10.1007/BF02187734</a>.","ieee":"H. Edelsbrunner, “The upper envelope of piecewise linear functions: Tight bounds on the number of faces ,” <i>Discrete &#38; Computational Geometry</i>, 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 . <i>Discrete &#38; Computational Geometry</i>. 1989;4(4):337-343. doi:<a href=\"https://doi.org/10.1007/BF02187734\">10.1007/BF02187734</a>","chicago":"Edelsbrunner, Herbert. “The Upper Envelope of Piecewise Linear Functions: Tight Bounds on the Number of Faces .” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187734\">https://doi.org/10.1007/BF02187734</a>.","ista":"Edelsbrunner H. 1989. The upper envelope of piecewise linear functions: Tight bounds on the number of faces . Discrete &#38; Computational Geometry. 4(4), 337–343.","short":"H. Edelsbrunner, Discrete &#38; Computational Geometry 4 (1989) 337–343."},"status":"public","date_created":"2018-12-11T12:06:51Z","oa_version":"Published Version","main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02187734"}],"article_type":"original","publist_id":"2034","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","author":[{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","orcid":"0000-0002-9823-6833"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"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","date_updated":"2022-02-10T11:08:12Z","publication":"Discrete & Computational Geometry","page":"337 - 343","type":"journal_article","day":"01","date_published":"1989-11-01T00:00:00Z","intvolume":"         4","publication_status":"published"},{"article_processing_charge":"No","_id":"4088","quality_controlled":"1","oa":1,"citation":{"ieee":"H. Edelsbrunner <i>et al.</i>, “Implicitly representing arrangements of lines or segments,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 433–466, 1989.","mla":"Edelsbrunner, Herbert, et al. “Implicitly Representing Arrangements of Lines or Segments.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 433–66, doi:<a href=\"https://doi.org/10.1007/BF02187742\">10.1007/BF02187742</a>.","ama":"Edelsbrunner H, Guibas L, Hershberger J, et al. Implicitly representing arrangements of lines or segments. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):433-466. doi:<a href=\"https://doi.org/10.1007/BF02187742\">10.1007/BF02187742</a>","apa":"Edelsbrunner, H., Guibas, L., Hershberger, J., Seidel, R., Sharir, M., Snoeyink, J., &#38; Welzl, E. (1989). Implicitly representing arrangements of lines or segments. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187742\">https://doi.org/10.1007/BF02187742</a>","short":"H. Edelsbrunner, L. Guibas, J. Hershberger, R. Seidel, M. Sharir, J. Snoeyink, E. Welzl, Discrete &#38; 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 &#38; Computational Geometry. 4(1), 433–466.","chicago":"Edelsbrunner, Herbert, Leonidas Guibas, John Hershberger, Raimund Seidel, Micha Sharir, Jack Snoeyink, and Emo Welzl. “Implicitly Representing Arrangements of Lines or Segments.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187742\">https://doi.org/10.1007/BF02187742</a>."},"issue":"1","month":"12","date_created":"2018-12-11T12:06:52Z","status":"public","doi":"10.1007/BF02187742","language":[{"iso":"eng"}],"volume":4,"title":"Implicitly representing arrangements of lines or segments","publisher":"Springer","abstract":[{"lang":"eng","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."}],"scopus_import":"1","year":"1989","extern":"1","date_published":"1989-12-01T00:00:00Z","page":"433 - 466","type":"journal_article","day":"01","intvolume":"         4","publication_status":"published","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publist_id":"2036","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"author":[{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"first_name":"Leonidas","full_name":"Guibas, Leonidas","last_name":"Guibas"},{"last_name":"Hershberger","full_name":"Hershberger, John","first_name":"John"},{"first_name":"Raimund","full_name":"Seidel, Raimund","last_name":"Seidel"},{"last_name":"Sharir","first_name":"Micha","full_name":"Sharir, Micha"},{"last_name":"Snoeyink","full_name":"Snoeyink, Jack","first_name":"Jack"},{"last_name":"Welzl","first_name":"Emo","full_name":"Welzl, Emo"}],"oa_version":"Published Version","main_file_link":[{"open_access":"1","url":"https://link.springer.com/article/10.1007/BF02187742"}],"article_type":"original","publication":"Discrete & Computational Geometry","date_updated":"2022-02-10T15:03:48Z","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."},{"oa":1,"_id":"4089","article_processing_charge":"No","quality_controlled":"1","volume":4,"language":[{"iso":"eng"}],"doi":"10.1007/BF02187745","status":"public","date_created":"2018-12-11T12:06:52Z","month":"12","citation":{"mla":"Edelsbrunner, Herbert, et al. “On Arrangements of Jordan Arcs with Three Intersections per Pair.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 523–39, doi:<a href=\"https://doi.org/10.1007/BF02187745\">10.1007/BF02187745</a>.","ieee":"H. Edelsbrunner <i>et al.</i>, “On arrangements of Jordan arcs with three intersections per pair,” <i>Discrete &#38; Computational Geometry</i>, 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. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):523-539. doi:<a href=\"https://doi.org/10.1007/BF02187745\">10.1007/BF02187745</a>","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. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187745\">https://doi.org/10.1007/BF02187745</a>","short":"H. Edelsbrunner, L. Guibas, J. Hershberger, J. Pach, R. Pollack, R. Seidel, M. Sharir, J. Snoeyink, Discrete &#38; Computational Geometry 4 (1989) 523–539.","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 &#38; Computational Geometry. 4(1), 523–539.","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.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187745\">https://doi.org/10.1007/BF02187745</a>."},"issue":"1","abstract":[{"lang":"eng","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."}],"publisher":"Springer","title":"On arrangements of Jordan arcs with three intersections per pair","extern":"1","year":"1989","scopus_import":"1","day":"01","page":"523 - 539","type":"journal_article","date_published":"1989-12-01T00:00:00Z","publication_status":"published","intvolume":"         4","article_type":"original","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187745","open_access":"1"}],"oa_version":"Published Version","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"last_name":"Guibas","full_name":"Guibas, Leonidas","first_name":"Leonidas"},{"last_name":"Hershberger","first_name":"John","full_name":"Hershberger, John"},{"full_name":"Pach, János","first_name":"János","last_name":"Pach"},{"last_name":"Pollack","first_name":"Richard","full_name":"Pollack, Richard"},{"last_name":"Seidel","full_name":"Seidel, Raimund","first_name":"Raimund"},{"first_name":"Micha","full_name":"Sharir, Micha","last_name":"Sharir"},{"last_name":"Snoeyink","full_name":"Snoeyink, Jack","first_name":"Jack"}],"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publist_id":"2037","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","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.","date_updated":"2022-02-10T15:40:04Z","publication":"Discrete & Computational Geometry"},{"_id":"4093","article_processing_charge":"No","quality_controlled":"1","volume":4,"language":[{"iso":"eng"}],"doi":"10.1007/BF02187720","status":"public","date_created":"2018-12-11T12:06:54Z","month":"03","citation":{"ama":"Chazelle B, Edelsbrunner H, Guibas L. The complexity of cutting complexes. <i>Discrete &#38; Computational Geometry</i>. 1989;4(1):139-181. doi:<a href=\"https://doi.org/10.1007/BF02187720\">10.1007/BF02187720</a>","ieee":"B. Chazelle, H. Edelsbrunner, and L. Guibas, “The complexity of cutting complexes,” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1. Springer, pp. 139–181, 1989.","mla":"Chazelle, Bernard, et al. “The Complexity of Cutting Complexes.” <i>Discrete &#38; Computational Geometry</i>, vol. 4, no. 1, Springer, 1989, pp. 139–81, doi:<a href=\"https://doi.org/10.1007/BF02187720\">10.1007/BF02187720</a>.","apa":"Chazelle, B., Edelsbrunner, H., &#38; Guibas, L. (1989). The complexity of cutting complexes. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187720\">https://doi.org/10.1007/BF02187720</a>","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, Discrete &#38; Computational Geometry 4 (1989) 139–181.","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, and Leonidas Guibas. “The Complexity of Cutting Complexes.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1989. <a href=\"https://doi.org/10.1007/BF02187720\">https://doi.org/10.1007/BF02187720</a>.","ista":"Chazelle B, Edelsbrunner H, Guibas L. 1989. The complexity of cutting complexes. Discrete &#38; Computational Geometry. 4(1), 139–181."},"issue":"1","abstract":[{"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.","lang":"eng"}],"publisher":"Springer","title":"The complexity of cutting complexes","extern":"1","year":"1989","day":"01","type":"journal_article","page":"139 - 181","date_published":"1989-03-01T00:00:00Z","publication_status":"published","intvolume":"         4","oa_version":"None","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02187720"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"author":[{"first_name":"Bernard","full_name":"Chazelle, Bernard","last_name":"Chazelle"},{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"full_name":"Guibas, Leonidas","first_name":"Leonidas","last_name":"Guibas"}],"publist_id":"2032","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","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.","date_updated":"2022-02-10T10:25:57Z","publication":"Discrete & Computational Geometry"},{"_id":"4100","article_processing_charge":"No","quality_controlled":"1","month":"01","issue":"1","citation":{"apa":"Chazelle, B., &#38; Edelsbrunner, H. (1987). Linear space data structures for two types of range search. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187875\">https://doi.org/10.1007/BF02187875</a>","mla":"Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures for Two Types of Range Search.” <i>Discrete &#38; Computational Geometry</i>, vol. 2, no. 1, Springer, 1987, pp. 113–26, doi:<a href=\"https://doi.org/10.1007/BF02187875\">10.1007/BF02187875</a>.","ieee":"B. Chazelle and H. Edelsbrunner, “Linear space data structures for two types of range search,” <i>Discrete &#38; Computational Geometry</i>, vol. 2, no. 1. Springer, pp. 113–126, 1987.","ama":"Chazelle B, Edelsbrunner H. Linear space data structures for two types of range search. <i>Discrete &#38; Computational Geometry</i>. 1987;2(1):113-126. doi:<a href=\"https://doi.org/10.1007/BF02187875\">10.1007/BF02187875</a>","chicago":"Chazelle, Bernard, and Herbert Edelsbrunner. “Linear Space Data Structures for Two Types of Range Search.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1987. <a href=\"https://doi.org/10.1007/BF02187875\">https://doi.org/10.1007/BF02187875</a>.","ista":"Chazelle B, Edelsbrunner H. 1987. Linear space data structures for two types of range search. Discrete &#38; Computational Geometry. 2(1), 113–126.","short":"B. Chazelle, H. Edelsbrunner, Discrete &#38; Computational Geometry 2 (1987) 113–126."},"status":"public","date_created":"2018-12-11T12:06:56Z","doi":"10.1007/BF02187875","volume":2,"language":[{"iso":"eng"}],"title":"Linear space data structures for two types of range search","publisher":"Springer","abstract":[{"lang":"eng","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"}],"year":"1987","scopus_import":"1","extern":"1","date_published":"1987-01-01T00:00:00Z","page":"113 - 126","type":"journal_article","day":"01","intvolume":"         2","publication_status":"published","publist_id":"2022","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","author":[{"first_name":"Bernard","full_name":"Chazelle, Bernard","last_name":"Chazelle"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"oa_version":"None","article_type":"original","publication":"Discrete & Computational Geometry","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.","date_updated":"2022-02-03T11:07:26Z"},{"title":"Voronoi diagrams and arrangements","publisher":"Springer","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"}],"year":"1986","extern":"1","quality_controlled":"1","article_processing_charge":"No","_id":"4108","citation":{"ama":"Edelsbrunner H, Seidel R. Voronoi diagrams and arrangements. <i>Discrete &#38; Computational Geometry</i>. 1986;1(1):25-44. doi:<a href=\"https://doi.org/10.1007/BF02187681\">10.1007/BF02187681</a>","mla":"Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.” <i>Discrete &#38; Computational Geometry</i>, vol. 1, no. 1, Springer, 1986, pp. 25–44, doi:<a href=\"https://doi.org/10.1007/BF02187681\">10.1007/BF02187681</a>.","ieee":"H. Edelsbrunner and R. Seidel, “Voronoi diagrams and arrangements,” <i>Discrete &#38; Computational Geometry</i>, vol. 1, no. 1. Springer, pp. 25–44, 1986.","apa":"Edelsbrunner, H., &#38; Seidel, R. (1986). Voronoi diagrams and arrangements. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02187681\">https://doi.org/10.1007/BF02187681</a>","short":"H. Edelsbrunner, R. Seidel, Discrete &#38; Computational Geometry 1 (1986) 25–44.","ista":"Edelsbrunner H, Seidel R. 1986. Voronoi diagrams and arrangements. Discrete &#38; Computational Geometry. 1(1), 25–44.","chicago":"Edelsbrunner, Herbert, and Raimund Seidel. “Voronoi Diagrams and Arrangements.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1986. <a href=\"https://doi.org/10.1007/BF02187681\">https://doi.org/10.1007/BF02187681</a>."},"issue":"1","month":"01","date_created":"2018-12-11T12:06:59Z","status":"public","doi":"10.1007/BF02187681","language":[{"iso":"eng"}],"volume":1,"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","publist_id":"2012","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"author":[{"orcid":"0000-0002-9823-6833","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert","first_name":"Herbert"},{"first_name":"Raimund","full_name":"Seidel, Raimund","last_name":"Seidel"}],"oa_version":"None","article_type":"original","publication":"Discrete & Computational Geometry","date_updated":"2022-02-01T08:53:39Z","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. ","date_published":"1986-01-01T00:00:00Z","page":"25 - 44","type":"journal_article","day":"01","intvolume":"         1","publication_status":"published"}]