[{"type":"journal_article","oa_version":"Published Version","article_type":"original","title":"The multi-cover persistence of Euclidean balls","department":[{"_id":"HeEd"}],"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","page":"1296–1313","project":[{"call_identifier":"H2020","grant_number":"788183","name":"Alpha Shape Theory Extended","_id":"266A2E9E-B435-11E9-9278-68D0E5697425"},{"_id":"2561EBF4-B435-11E9-9278-68D0E5697425","call_identifier":"FWF","grant_number":"I02979-N35","name":"Persistence and stability of geometric complexes"}],"ec_funded":1,"intvolume":"        65","scopus_import":"1","doi":"10.1007/s00454-021-00281-9","status":"public","publication_status":"published","date_updated":"2025-06-12T06:36:54Z","language":[{"iso":"eng"}],"article_processing_charge":"Yes (via OA deal)","ddc":["516"],"_id":"9317","file":[{"relation":"main_file","file_size":677704,"file_id":"10394","creator":"cchlebak","success":1,"date_created":"2021-12-01T10:56:53Z","content_type":"application/pdf","date_updated":"2021-12-01T10:56:53Z","access_level":"open_access","checksum":"59b4e1e827e494209bcb4aae22e1d347","file_name":"2021_DisCompGeo_Edelsbrunner_Osang.pdf"}],"date_created":"2021-04-11T22:01:15Z","day":"31","year":"2021","volume":65,"month":"03","quality_controlled":"1","author":[{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert"},{"first_name":"Georg F","last_name":"Osang","id":"464B40D6-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8882-5116","full_name":"Osang, Georg F"}],"related_material":{"record":[{"relation":"earlier_version","status":"public","id":"187"}]},"oa":1,"publication":"Discrete and Computational Geometry","citation":{"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>.","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>","ista":"Edelsbrunner H, Osang GF. 2021. The multi-cover persistence of Euclidean balls. Discrete and Computational Geometry. 65, 1296–1313.","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.","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>."},"abstract":[{"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.","lang":"eng"}],"corr_author":"1","has_accepted_license":"1","isi":1,"publisher":"Springer Nature","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"date_published":"2021-03-31T00:00:00Z","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).","external_id":{"pmid":["34720303"],"isi":["000635460400001"]},"file_date_updated":"2021-12-01T10:56:53Z","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"pmid":1},{"quality_controlled":"1","related_material":{"record":[{"id":"683","status":"public","relation":"earlier_version"},{"relation":"dissertation_contains","status":"public","id":"7944"}]},"author":[{"last_name":"Lubiw","first_name":"Anna","full_name":"Lubiw, Anna"},{"full_name":"Masárová, Zuzana","id":"45CFE238-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-6660-1322","last_name":"Masárová","first_name":"Zuzana"},{"id":"36690CA2-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-1494-0568","first_name":"Uli","last_name":"Wagner","full_name":"Wagner, Uli"}],"month":"06","oa":1,"day":"01","year":"2019","date_created":"2019-02-14T11:54:08Z","volume":61,"isi":1,"publisher":"Springer Nature","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"has_accepted_license":"1","date_published":"2019-06-01T00:00:00Z","file_date_updated":"2020-07-14T12:47:14Z","external_id":{"arxiv":["1710.02741"],"isi":["000466130000009"]},"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"publication":"Discrete & Computational Geometry","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."}],"corr_author":"1","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.","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>.","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>","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>","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.","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."},"page":"880-898","arxiv":1,"user_id":"c635000d-4b10-11ee-a964-aac5a93f6ac1","project":[{"_id":"B67AFEDC-15C9-11EA-A837-991A96BB2854","name":"IST Austria Open Access Fund"}],"article_type":"original","type":"journal_article","oa_version":"Published Version","department":[{"_id":"UlWa"}],"title":"A proof of the orbit conjecture for flipping edge-labelled triangulations","ddc":["000"],"_id":"5986","file":[{"access_level":"open_access","date_updated":"2020-07-14T12:47:14Z","file_name":"2018_DiscreteGeometry_Lubiw.pdf","checksum":"e1bff88f1d77001b53b78c485ce048d7","content_type":"application/pdf","date_created":"2019-02-14T11:57:22Z","file_id":"5988","creator":"dernst","file_size":556276,"relation":"main_file"}],"article_processing_charge":"Yes (via OA deal)","language":[{"iso":"eng"}],"doi":"10.1007/s00454-018-0035-8","scopus_import":"1","intvolume":"        61","date_updated":"2026-04-08T07:23:01Z","status":"public","publication_status":"published","issue":"4"},{"ddc":["516","000"],"_id":"1064","file":[{"creator":"dernst","file_id":"5844","file_size":482518,"relation":"main_file","date_updated":"2019-01-18T09:27:36Z","access_level":"open_access","file_name":"2018_DiscreteComp_Akopyan.pdf","success":1,"date_created":"2019-01-18T09:27:36Z","content_type":"application/pdf"}],"language":[{"iso":"eng"}],"article_processing_charge":"Yes (via OA deal)","date_updated":"2026-05-20T10:19:33Z","status":"public","issue":"4","publication_status":"published","doi":"10.1007/s00454-017-9883-x","scopus_import":"1","intvolume":"        59","ec_funded":1,"project":[{"_id":"25681D80-B435-11E9-9278-68D0E5697425","grant_number":"291734","name":"International IST Postdoc Fellowship Programme","call_identifier":"FP7"}],"page":"1001-1009","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"HeEd"}],"title":"On the circle covering theorem by A.W. Goodman and R.E. Goodman","article_type":"original","type":"journal_article","oa_version":"Published Version","publist_id":"6324","file_date_updated":"2019-01-18T09:27:36Z","date_published":"2018-06-01T00:00:00Z","external_id":{"isi":["000432205500011"]},"publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"isi":1,"publisher":"Springer","tmp":{"short":"CC BY (4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","image":"/images/cc_by.png"},"has_accepted_license":"1","abstract":[{"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.","lang":"eng"}],"corr_author":"1","citation":{"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.","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>","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>","short":"A. Akopyan, A. Balitskiy, M. Grigorev, Discrete &#38; Computational Geometry 59 (2018) 1001–1009.","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>.","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."},"publication":"Discrete & Computational Geometry","oa":1,"quality_controlled":"1","author":[{"first_name":"Arseniy","last_name":"Akopyan","id":"430D2C90-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-2548-617X","full_name":"Akopyan, Arseniy"},{"first_name":"Alexey","last_name":"Balitskiy","full_name":"Balitskiy, Alexey"},{"last_name":"Grigorev","first_name":"Mikhail","full_name":"Grigorev, Mikhail"}],"month":"06","volume":59,"day":"01","year":"2018","date_created":"2018-12-11T11:49:57Z"},{"date_updated":"2026-07-14T11:14:51Z","status":"public","issue":"3","publication_status":"published","doi":"10.1007/s00454-016-9843-x","scopus_import":"1","intvolume":"        58","_id":"22198","article_processing_charge":"No","language":[{"iso":"eng"}],"OA_type":"green","title":"Packings of equal disks in a square torus","article_type":"original","type":"journal_article","oa_version":"Preprint","page":"614-642","arxiv":1,"user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","extern":"1","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."}],"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>","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>.","short":"R. Connelly, M. Funkhouser, V.Z. Kuperberg, E. Solomonides, Discrete &#38; Computational Geometry 58 (2017) 614–642.","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.","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.","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>.","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>"},"main_file_link":[{"url":"https://doi.org/10.48550/arXiv.1512.08762"}],"publication":"Discrete & Computational Geometry","external_id":{"arxiv":["1512.08762"]},"date_published":"2017-01-09T00:00:00Z","OA_place":"repository","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publisher":"Springer Nature","volume":58,"day":"09","year":"2017","date_created":"2026-06-29T12:58:50Z","quality_controlled":"1","author":[{"first_name":"Robert","last_name":"Connelly","full_name":"Connelly, Robert"},{"full_name":"Funkhouser, Matthew","first_name":"Matthew","last_name":"Funkhouser"},{"id":"c3bac823-112d-11f0-a3f5-c264f852e697","first_name":"Vivian Zieve","last_name":"Kuperberg","full_name":"Kuperberg, Vivian Zieve"},{"first_name":"Evan","last_name":"Solomonides","full_name":"Solomonides, Evan"}],"month":"01"},{"page":"797 - 822","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","article_type":"original","type":"journal_article","oa_version":"Published Version","department":[{"_id":"HeEd"}],"title":"Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions","ddc":["500"],"_id":"2815","language":[{"iso":"eng"}],"article_processing_charge":"No","scopus_import":"1","doi":"10.1007/s00454-013-9517-x","intvolume":"        49","date_updated":"2026-06-18T18:35:33Z","status":"public","issue":"4","publication_status":"published","quality_controlled":"1","related_material":{"record":[{"relation":"earlier_version","status":"public","id":"3134"}]},"author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"id":"F65D502E-E68D-11E9-9252-C644099818F6","last_name":"Fasy","first_name":"Brittany Terese","full_name":"Fasy, Brittany Terese"},{"last_name":"Rote","first_name":"Günter","full_name":"Rote, Günter"}],"month":"06","oa":1,"day":"01","year":"2013","date_created":"2018-12-11T11:59:44Z","volume":49,"publisher":"Springer","isi":1,"publist_id":"3991","date_published":"2013-06-01T00:00:00Z","external_id":{"isi":["000320672400005"]},"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_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"main_file_link":[{"url":"https://doi.org/10.1007/s00454-013-9517-x","open_access":"1"}],"publication":"Discrete & Computational Geometry","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."}],"corr_author":"1","citation":{"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>","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>.","short":"H. Edelsbrunner, B.T. Fasy, G. Rote, Discrete &#38; Computational Geometry 49 (2013) 797–822.","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>.","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>","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."}},{"quality_controlled":"1","author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"full_name":"Letscher, David","last_name":"Letscher","first_name":"David"},{"last_name":"Zomorodian","first_name":"Afra","full_name":"Zomorodian, Afra"}],"month":"12","day":"01","year":"2002","date_created":"2018-12-11T12:06:20Z","volume":28,"publisher":"Springer","publist_id":"2130","date_published":"2002-12-01T00:00:00Z","acknowledgement":"We thank Jeff Erickson and John Harer for helpful discussions during early stages of this\r\npaper. We also thank Daniel Huson for the zeolite dataset Z, Thomas LaBean for the DNA\r\ndataset D, and the Stanford Graphics Lab for the Buddha dataset S. To generate the bone\r\ndataset B, we sampled an iso-surface generated by Dominique Attali. The volume data\r\nTopological Persistence and Simplification 533 was provided by Francoise Peyrin from CNRS CREATIS in Lyon and was issued from ¸ Synchrotron Radiation Microtomography from the ID19 beamline at ESRF in Grenoble.\r\nWe generated Fig. 17 using the Protein Explorer [6].","publication_identifier":{"issn":["0179-5376"]},"publication":"Discrete & Computational Geometry","abstract":[{"lang":"eng","text":"We formalize a notion of topological simplification within the framework of a filtration, which is the history of a growing complex. We classify a topological change that happens during growth as either a feature or noise depending on its lifetime or persistence within the filtration. We give fast algorithms for computing persistence and experimental evidence for their speed and utility."}],"citation":{"ama":"Edelsbrunner H, Letscher D, Zomorodian A. Topological persistence and simplification. <i>Discrete &#38; Computational Geometry</i>. 2002;28(4):511-533. doi:<a href=\"https://doi.org/10.1007/s00454-002-2885-2\">10.1007/s00454-002-2885-2</a>","mla":"Edelsbrunner, Herbert, et al. “Topological Persistence and Simplification.” <i>Discrete &#38; Computational Geometry</i>, vol. 28, no. 4, Springer, 2002, pp. 511–33, doi:<a href=\"https://doi.org/10.1007/s00454-002-2885-2\">10.1007/s00454-002-2885-2</a>.","ista":"Edelsbrunner H, Letscher D, Zomorodian A. 2002. Topological persistence and simplification. Discrete &#38; Computational Geometry. 28(4), 511–533.","ieee":"H. Edelsbrunner, D. Letscher, and A. Zomorodian, “Topological persistence and simplification,” <i>Discrete &#38; Computational Geometry</i>, vol. 28, no. 4. Springer, pp. 511–533, 2002.","chicago":"Edelsbrunner, Herbert, David Letscher, and Afra Zomorodian. “Topological Persistence and Simplification.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2002. <a href=\"https://doi.org/10.1007/s00454-002-2885-2\">https://doi.org/10.1007/s00454-002-2885-2</a>.","short":"H. Edelsbrunner, D. Letscher, A. Zomorodian, Discrete &#38; Computational Geometry 28 (2002) 511–533.","apa":"Edelsbrunner, H., Letscher, D., &#38; Zomorodian, A. (2002). Topological persistence and simplification. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-002-2885-2\">https://doi.org/10.1007/s00454-002-2885-2</a>"},"page":"511 - 533","extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","article_type":"original","type":"journal_article","oa_version":"None","title":"Topological persistence and simplification","_id":"3996","language":[{"iso":"eng"}],"article_processing_charge":"No","scopus_import":"1","doi":"10.1007/s00454-002-2885-2","intvolume":"        28","date_updated":"2023-06-13T11:41:19Z","status":"public","publication_status":"published","issue":"4"},{"_id":"2419","article_processing_charge":"No","language":[{"iso":"eng"}],"date_updated":"2023-05-24T13:13:51Z","publication_status":"published","issue":"2","status":"public","scopus_import":"1","doi":"10.1007/s00454-001-0028-9","intvolume":"        26","page":"205 - 219","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","title":"A continuous analogue of the Upper Bound Theorem","article_type":"original","oa_version":"None","type":"journal_article","publist_id":"4506","publication_identifier":{"issn":["0179-5376"]},"acknowledgement":"We are indebted to Rolf Schneider for many helpful remarks and in particular for bringing reference [6] to our attention","date_published":"2001-01-01T00:00:00Z","publisher":"Springer","abstract":[{"text":"For an absolutely continuous probability measure μ. on ℝd and a nonnegative integer k, let S̃k(μ, 0) denote the probability that the convex hull of k + d + 1 random points which are i.i.d. according to μ contains the origin 0. For d and k given, we determine a tight upper bound on S̃k(μ, 0), and we characterize the measures in ℝd which attain this bound. As we will see, this result can be considered a continuous analogue of the Upper Bound Theorem for the maximal number of faces of convex polytopes with a given number of vertices. For our proof we introduce so-called h-functions, continuous counterparts of h-vectors of simplicial convex polytopes.","lang":"eng"}],"citation":{"ista":"Wagner U, Welzl E. 2001. A continuous analogue of the Upper Bound Theorem. Discrete &#38; Computational Geometry. 26(2), 205–219.","ama":"Wagner U, Welzl E. A continuous analogue of the Upper Bound Theorem. <i>Discrete &#38; Computational Geometry</i>. 2001;26(2):205-219. doi:<a href=\"https://doi.org/10.1007/s00454-001-0028-9\">10.1007/s00454-001-0028-9</a>","mla":"Wagner, Uli, and Emo Welzl. “A Continuous Analogue of the Upper Bound Theorem.” <i>Discrete &#38; Computational Geometry</i>, vol. 26, no. 2, Springer, 2001, pp. 205–19, doi:<a href=\"https://doi.org/10.1007/s00454-001-0028-9\">10.1007/s00454-001-0028-9</a>.","chicago":"Wagner, Uli, and Emo Welzl. “A Continuous Analogue of the Upper Bound Theorem.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2001. <a href=\"https://doi.org/10.1007/s00454-001-0028-9\">https://doi.org/10.1007/s00454-001-0028-9</a>.","short":"U. Wagner, E. Welzl, Discrete &#38; Computational Geometry 26 (2001) 205–219.","apa":"Wagner, U., &#38; Welzl, E. (2001). A continuous analogue of the Upper Bound Theorem. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-001-0028-9\">https://doi.org/10.1007/s00454-001-0028-9</a>","ieee":"U. Wagner and E. Welzl, “A continuous analogue of the Upper Bound Theorem,” <i>Discrete &#38; Computational Geometry</i>, vol. 26, no. 2. Springer, pp. 205–219, 2001."},"publication":"Discrete & Computational Geometry","author":[{"last_name":"Wagner","first_name":"Uli","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"}],"quality_controlled":"1","month":"01","volume":26,"year":"2001","day":"01","date_created":"2018-12-11T11:57:33Z"},{"citation":{"ieee":"H. Cheng, T. Dey, H. Edelsbrunner, and J. Sullivan, “Dynamic skin triangulation,” <i>Discrete &#38; Computational Geometry</i>, vol. 25, no. 4. Springer, pp. 525–568, 2001.","short":"H. Cheng, T. Dey, H. Edelsbrunner, J. Sullivan, Discrete &#38; Computational Geometry 25 (2001) 525–568.","chicago":"Cheng, Ho, Tamal Dey, Herbert Edelsbrunner, and John Sullivan. “Dynamic Skin Triangulation.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2001. <a href=\"https://doi.org/10.1007/s00454-001-0007-1\">https://doi.org/10.1007/s00454-001-0007-1</a>.","apa":"Cheng, H., Dey, T., Edelsbrunner, H., &#38; Sullivan, J. (2001). Dynamic skin triangulation. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s00454-001-0007-1\">https://doi.org/10.1007/s00454-001-0007-1</a>","ama":"Cheng H, Dey T, Edelsbrunner H, Sullivan J. Dynamic skin triangulation. <i>Discrete &#38; Computational Geometry</i>. 2001;25(4):525-568. doi:<a href=\"https://doi.org/10.1007/s00454-001-0007-1\">10.1007/s00454-001-0007-1</a>","mla":"Cheng, Ho, et al. “Dynamic Skin Triangulation.” <i>Discrete &#38; Computational Geometry</i>, vol. 25, no. 4, Springer, 2001, pp. 525–68, doi:<a href=\"https://doi.org/10.1007/s00454-001-0007-1\">10.1007/s00454-001-0007-1</a>.","ista":"Cheng H, Dey T, Edelsbrunner H, Sullivan J. 2001. Dynamic skin triangulation. Discrete &#38; Computational Geometry. 25(4), 525–568."},"abstract":[{"lang":"eng","text":"This paper describes an algorithm for maintaining an approximating triangulation of a deforming surface in R 3 . The surface is the envelope of an infinite family of spheres defined and controlled by a finite collection of weighted points. The triangulation adapts dynamically to changing shape, curvature, and topology of the surface. "}],"publication":"Discrete & Computational Geometry","acknowledgement":"NSF under grant DMS- 98-73945, ARO under grant DAAG55-98-1-0177, NSF under grants CCR-96- 19542 and CCR-97-12088.","date_published":"2001-04-04T00:00:00Z","publication_identifier":{"issn":["0179-5376"]},"publist_id":"2122","publisher":"Springer","volume":25,"date_created":"2018-12-11T12:06:24Z","day":"04","year":"2001","month":"04","quality_controlled":"1","author":[{"full_name":"Cheng, Ho","first_name":"Ho","last_name":"Cheng"},{"last_name":"Dey","first_name":"Tamal","full_name":"Dey, Tamal"},{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"full_name":"Sullivan, John","last_name":"Sullivan","first_name":"John"}],"status":"public","publication_status":"published","issue":"4","date_updated":"2023-05-10T12:45:59Z","intvolume":"        25","doi":"10.1007/s00454-001-0007-1","scopus_import":"1","article_processing_charge":"No","language":[{"iso":"eng"}],"_id":"4007","title":"Dynamic skin triangulation","type":"journal_article","oa_version":"None","article_type":"original","extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","page":"525 - 568"},{"user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","page":"707 - 719","title":"Edgewise subdivision of a simplex","oa_version":"None","type":"journal_article","article_type":"original","language":[{"iso":"eng"}],"article_processing_charge":"No","_id":"4004","publication_status":"published","issue":"4","status":"public","date_updated":"2023-05-02T11:43:59Z","intvolume":"        24","scopus_import":"1","doi":"10.1007/s004540010063","month":"12","author":[{"last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"first_name":"Daniel","last_name":"Grayson","full_name":"Grayson, Daniel"}],"quality_controlled":"1","volume":24,"date_created":"2018-12-11T12:06:23Z","year":"2000","day":"01","publication_identifier":{"issn":["0179-5376"]},"acknowledgement":"NSF under Grant DMS 98-73945, NSF under Grant CCR-96-19542 and by ARO under Grant DAAG55- 98-1-0177.","date_published":"2000-12-01T00:00:00Z","publist_id":"2119","publisher":"Springer","citation":{"short":"H. Edelsbrunner, D. Grayson, Discrete &#38; Computational Geometry 24 (2000) 707–719.","chicago":"Edelsbrunner, Herbert, and Daniel Grayson. “Edgewise Subdivision of a Simplex.” <i>Discrete &#38; Computational Geometry</i>. Springer, 2000. <a href=\"https://doi.org/10.1007/s004540010063\">https://doi.org/10.1007/s004540010063</a>.","apa":"Edelsbrunner, H., &#38; Grayson, D. (2000). Edgewise subdivision of a simplex. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/s004540010063\">https://doi.org/10.1007/s004540010063</a>","ieee":"H. Edelsbrunner and D. Grayson, “Edgewise subdivision of a simplex,” <i>Discrete &#38; Computational Geometry</i>, vol. 24, no. 4. Springer, pp. 707–719, 2000.","ista":"Edelsbrunner H, Grayson D. 2000. Edgewise subdivision of a simplex. Discrete &#38; Computational Geometry. 24(4), 707–719.","ama":"Edelsbrunner H, Grayson D. Edgewise subdivision of a simplex. <i>Discrete &#38; Computational Geometry</i>. 2000;24(4):707-719. doi:<a href=\"https://doi.org/10.1007/s004540010063\">10.1007/s004540010063</a>","mla":"Edelsbrunner, Herbert, and Daniel Grayson. “Edgewise Subdivision of a Simplex.” <i>Discrete &#38; Computational Geometry</i>, vol. 24, no. 4, Springer, 2000, pp. 707–19, doi:<a href=\"https://doi.org/10.1007/s004540010063\">10.1007/s004540010063</a>."},"abstract":[{"lang":"eng","text":"In this paper we introduce the abacus model of a simplex and use it to subdivide a d-simplex into k(d) d-simplices all of the same volume and shape characteristics. The construction is an extension of the subdivision method of Freudenthal [3] and has been used by Goodman and Peters [4] to design smooth manifolds."}],"publication":"Discrete & Computational Geometry"},{"publication":"Discrete & Computational Geometry","abstract":[{"lang":"eng","text":"A new paradigm for designing smooth surfaces is described. A finite set of points with weights specifies a closed surface in space referred to as skin. It consists of one or more components, each tangent continuous and free of self-intersections and intersections with other components. The skin varies continuously with the weights and locations of the points, and the variation includes the possibility of a topology change facilitated by the violation of tangent continuity at a single point in space and time. Applications of the skin to molecular modeling and to geometric deformation are discussed."}],"citation":{"ieee":"H. Edelsbrunner, “Deformable smooth surface design,” <i>Discrete &#38; Computational Geometry</i>, vol. 21, no. 1. Springer, pp. 87–115, 1999.","apa":"Edelsbrunner, H. (1999). Deformable smooth surface design. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/PL00009412\">https://doi.org/10.1007/PL00009412</a>","chicago":"Edelsbrunner, Herbert. “Deformable Smooth Surface Design.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1999. <a href=\"https://doi.org/10.1007/PL00009412\">https://doi.org/10.1007/PL00009412</a>.","short":"H. Edelsbrunner, Discrete &#38; Computational Geometry 21 (1999) 87–115.","mla":"Edelsbrunner, Herbert. “Deformable Smooth Surface Design.” <i>Discrete &#38; Computational Geometry</i>, vol. 21, no. 1, Springer, 1999, pp. 87–115, doi:<a href=\"https://doi.org/10.1007/PL00009412\">10.1007/PL00009412</a>.","ama":"Edelsbrunner H. Deformable smooth surface design. <i>Discrete &#38; Computational Geometry</i>. 1999;21(1):87-115. doi:<a href=\"https://doi.org/10.1007/PL00009412\">10.1007/PL00009412</a>","ista":"Edelsbrunner H. 1999. Deformable smooth surface design. Discrete &#38; Computational Geometry. 21(1), 87–115."},"publisher":"Springer","publist_id":"2115","date_published":"1999-01-01T00:00:00Z","publication_identifier":{"issn":["0179-5376"]},"day":"01","year":"1999","date_created":"2018-12-11T12:06:26Z","volume":21,"quality_controlled":"1","author":[{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"}],"month":"01","scopus_import":"1","doi":"10.1007/PL00009412","intvolume":"        21","date_updated":"2022-09-06T09:02:23Z","status":"public","publication_status":"published","issue":"1","_id":"4014","article_processing_charge":"No","language":[{"iso":"eng"}],"article_type":"original","type":"journal_article","oa_version":"None","title":"Deformable smooth surface design","page":"87 - 115","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1"},{"intvolume":"        17","doi":"10.1007/PL00009291","scopus_import":"1","status":"public","publication_status":"published","issue":"3","date_updated":"2022-08-18T14:08:38Z","language":[{"iso":"eng"}],"article_processing_charge":"No","_id":"4022","type":"journal_article","oa_version":"None","article_type":"original","title":"Cutting dense point sets in half","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","page":"243 - 255","publication":"Discrete & Computational Geometry","citation":{"ista":"Edelsbrunner H, Valtr P, Welzl E. 1997. Cutting dense point sets in half. Discrete &#38; Computational Geometry. 17(3), 243–255.","ama":"Edelsbrunner H, Valtr P, Welzl E. Cutting dense point sets in half. <i>Discrete &#38; Computational Geometry</i>. 1997;17(3):243-255. doi:<a href=\"https://doi.org/10.1007/PL00009291\">10.1007/PL00009291</a>","mla":"Edelsbrunner, Herbert, et al. “Cutting Dense Point Sets in Half.” <i>Discrete &#38; Computational Geometry</i>, vol. 17, no. 3, Springer, 1997, pp. 243–55, doi:<a href=\"https://doi.org/10.1007/PL00009291\">10.1007/PL00009291</a>.","short":"H. Edelsbrunner, P. Valtr, E. Welzl, Discrete &#38; Computational Geometry 17 (1997) 243–255.","chicago":"Edelsbrunner, Herbert, Pavel Valtr, and Emo Welzl. “Cutting Dense Point Sets in Half.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1997. <a href=\"https://doi.org/10.1007/PL00009291\">https://doi.org/10.1007/PL00009291</a>.","apa":"Edelsbrunner, H., Valtr, P., &#38; Welzl, E. (1997). Cutting dense point sets in half. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/PL00009291\">https://doi.org/10.1007/PL00009291</a>","ieee":"H. Edelsbrunner, P. Valtr, and E. Welzl, “Cutting dense point sets in half,” <i>Discrete &#38; Computational Geometry</i>, vol. 17, no. 3. Springer, pp. 243–255, 1997."},"abstract":[{"text":"A halving hyperplane of a set S of n points in R(d) contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two half-spaces. We prove bounds on the number of halving hyperplanes under the condition that the ratio of largest over smallest distance between any two points is at most delta n(1/d), delta some constant. Such a set S is called dense. In d = 2 dimensions the number of halving lines for a dense set can be as much as Omega(n log n), and it cannot exceed O (n(5/4)/log* n). The upper bound improves over the current best bound of O (n(3/2)/log* n) which holds more generally without any density assumption. In d = 3 dimensions we show that O (n(7/3)) is an upper bound on the number of halving planes for a dense set, The proof is based on a metric argument that can be extended to d greater than or equal to 4 dimensions, where it leads to O (n(d-2/d)) as an upper bound for the number of halving hyperplanes.","lang":"eng"}],"publisher":"Springer","date_published":"1997-04-01T00:00:00Z","acknowledgement":"Partially supported by the National Science Foundation, under Grant ASC-9200301 and the Alan T. Waterman award, Grant CCR-9118874.","publication_identifier":{"issn":["0179-5376"]},"publist_id":"2103","date_created":"2018-12-11T12:06:29Z","day":"01","year":"1997","volume":17,"month":"04","quality_controlled":"1","author":[{"full_name":"Edelsbrunner, Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner"},{"first_name":"Pavel","last_name":"Valtr","full_name":"Valtr, Pavel"},{"full_name":"Welzl, Emo","first_name":"Emo","last_name":"Welzl"}]},{"month":"04","author":[{"last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"first_name":"Edgar","last_name":"Ramos","full_name":"Ramos, Edgar"}],"quality_controlled":"1","volume":17,"date_created":"2018-12-11T12:06:30Z","year":"1997","day":"01","publication_identifier":{"issn":["0179-5376"]},"acknowledgement":"Supported by the National Science Foundation, under Grant ASC-9200301 and the Alan T. Waterman Award CCR-9118874.","date_published":"1997-04-01T00:00:00Z","publist_id":"2104","publisher":"Springer","citation":{"ama":"Edelsbrunner H, Ramos E. Inclusion-exclusion complexes for pseudodisk collections. <i>Discrete &#38; Computational Geometry</i>. 1997;17(3):287-306. doi:<a href=\"https://doi.org/10.1007/PL00009295\">10.1007/PL00009295</a>","mla":"Edelsbrunner, Herbert, and Edgar Ramos. “Inclusion-Exclusion Complexes for Pseudodisk Collections.” <i>Discrete &#38; Computational Geometry</i>, vol. 17, no. 3, Springer, 1997, pp. 287–306, doi:<a href=\"https://doi.org/10.1007/PL00009295\">10.1007/PL00009295</a>.","ista":"Edelsbrunner H, Ramos E. 1997. Inclusion-exclusion complexes for pseudodisk collections. Discrete &#38; Computational Geometry. 17(3), 287–306.","ieee":"H. Edelsbrunner and E. Ramos, “Inclusion-exclusion complexes for pseudodisk collections,” <i>Discrete &#38; Computational Geometry</i>, vol. 17, no. 3. Springer, pp. 287–306, 1997.","chicago":"Edelsbrunner, Herbert, and Edgar Ramos. “Inclusion-Exclusion Complexes for Pseudodisk Collections.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1997. <a href=\"https://doi.org/10.1007/PL00009295\">https://doi.org/10.1007/PL00009295</a>.","short":"H. Edelsbrunner, E. Ramos, Discrete &#38; Computational Geometry 17 (1997) 287–306.","apa":"Edelsbrunner, H., &#38; Ramos, E. (1997). Inclusion-exclusion complexes for pseudodisk collections. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/PL00009295\">https://doi.org/10.1007/PL00009295</a>"},"abstract":[{"lang":"eng","text":"Let B be a finite pseudodisk collection in the plane. By the principle of inclusion-exclusion, the area or any other measure of the union is [GRAPHICS] We show the existence of a two-dimensional abstract simplicial complex, X subset of or equal to 2(B), so the above relation holds even if X is substituted for 2(B). In addition, X can be embedded in R(2) SO its underlying space is homotopy equivalent to int Boolean OR B, and the frontier of X is isomorphic to the nerve of the set of boundary contributions."}],"publication":"Discrete & Computational Geometry","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","page":"287 - 306","title":"Inclusion-exclusion complexes for pseudodisk collections","oa_version":"None","type":"journal_article","article_type":"original","language":[{"iso":"eng"}],"article_processing_charge":"No","_id":"4023","publication_status":"published","issue":"3","status":"public","date_updated":"2022-08-18T14:39:39Z","intvolume":"        17","scopus_import":"1","doi":"10.1007/PL00009295"},{"scopus_import":"1","doi":"10.1007/BF02574053","intvolume":"        13","date_updated":"2022-06-27T08:14:48Z","issue":"1","publication_status":"published","status":"public","_id":"4028","article_processing_charge":"No","language":[{"iso":"eng"}],"article_type":"original","oa_version":"Published Version","type":"journal_article","title":"The union of balls and its dual shape","page":"415 - 440","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","publication":"Discrete & Computational Geometry","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02574053","open_access":"1"}],"abstract":[{"text":"Efficient algorithms are described for computing topological, combinatorial, and metric properties of the union of finitely many spherical balls in R(d) These algorithms are based on a simplicial complex dual to a decomposition of the union of balls using Voronoi cells, and on short inclusion-exclusion formulas derived from this complex. The algorithms are most relevant in R(3) where unions of finitely many balls are commonly used as models of molecules.","lang":"eng"}],"citation":{"ista":"Edelsbrunner H. 1995. The union of balls and its dual shape. Discrete &#38; Computational Geometry. 13(1), 415–440.","ama":"Edelsbrunner H. The union of balls and its dual shape. <i>Discrete &#38; Computational Geometry</i>. 1995;13(1):415-440. doi:<a href=\"https://doi.org/10.1007/BF02574053\">10.1007/BF02574053</a>","mla":"Edelsbrunner, Herbert. “The Union of Balls and Its Dual Shape.” <i>Discrete &#38; Computational Geometry</i>, vol. 13, no. 1, Springer, 1995, pp. 415–40, doi:<a href=\"https://doi.org/10.1007/BF02574053\">10.1007/BF02574053</a>.","chicago":"Edelsbrunner, Herbert. “The Union of Balls and Its Dual Shape.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1995. <a href=\"https://doi.org/10.1007/BF02574053\">https://doi.org/10.1007/BF02574053</a>.","short":"H. Edelsbrunner, Discrete &#38; Computational Geometry 13 (1995) 415–440.","apa":"Edelsbrunner, H. (1995). The union of balls and its dual shape. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02574053\">https://doi.org/10.1007/BF02574053</a>","ieee":"H. Edelsbrunner, “The union of balls and its dual shape,” <i>Discrete &#38; Computational Geometry</i>, vol. 13, no. 1. Springer, pp. 415–440, 1995."},"publisher":"Springer","publist_id":"2095","publication_identifier":{"issn":["0179-5376"]},"date_published":"1995-12-01T00:00:00Z","acknowledgement":"This work is supported by the National Science Foundation, under Grant ASC-9200301, and the Alan T. Waterman award, Grant CCR-9118874. Any opinions, findings, conclusions, or recommendations expressed in this publication are those of the author and do not necessarily reflect the view of the National Science Foundation.","year":"1995","day":"01","date_created":"2018-12-11T12:06:31Z","volume":13,"author":[{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"}],"quality_controlled":"1","month":"12","oa":1},{"month":"12","quality_controlled":"1","author":[{"full_name":"Chazelle, Bernard","first_name":"Bernard","last_name":"Chazelle"},{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Grigni, Michelangelo","last_name":"Grigni","first_name":"Michelangelo"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"},{"first_name":"Emo","last_name":"Welzl","full_name":"Welzl, Emo"}],"volume":13,"date_created":"2018-12-11T12:06:33Z","day":"01","year":"1995","date_published":"1995-12-01T00:00:00Z","acknowledgement":"The authors wish to express their gratitude for the support and hospitality of the DEC Palo Alto Systems Research Center.","publication_identifier":{"issn":["0179-5376"]},"publist_id":"2094","publisher":"Springer","citation":{"short":"B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, E. Welzl, Discrete &#38; Computational Geometry 13 (1995) 1–15.","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Michelangelo Grigni, Leonidas Guibas, Micha Sharir, and Emo Welzl. “Improved Bounds on Weak ε-Nets for Convex Sets.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1995. <a href=\"https://doi.org/10.1007/BF02574025\">https://doi.org/10.1007/BF02574025</a>.","apa":"Chazelle, B., Edelsbrunner, H., Grigni, M., Guibas, L., Sharir, M., &#38; Welzl, E. (1995). Improved bounds on weak ε-nets for convex sets. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02574025\">https://doi.org/10.1007/BF02574025</a>","ieee":"B. Chazelle, H. Edelsbrunner, M. Grigni, L. Guibas, M. Sharir, and E. Welzl, “Improved bounds on weak ε-nets for convex sets,” <i>Discrete &#38; Computational Geometry</i>, vol. 13, no. 1. Springer, pp. 1–15, 1995.","ista":"Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Sharir M, Welzl E. 1995. Improved bounds on weak ε-nets for convex sets. Discrete &#38; Computational Geometry. 13(1), 1–15.","ama":"Chazelle B, Edelsbrunner H, Grigni M, Guibas L, Sharir M, Welzl E. Improved bounds on weak ε-nets for convex sets. <i>Discrete &#38; Computational Geometry</i>. 1995;13(1):1-15. doi:<a href=\"https://doi.org/10.1007/BF02574025\">10.1007/BF02574025</a>","mla":"Chazelle, Bernard, et al. “Improved Bounds on Weak ε-Nets for Convex Sets.” <i>Discrete &#38; Computational Geometry</i>, vol. 13, no. 1, Springer, 1995, pp. 1–15, doi:<a href=\"https://doi.org/10.1007/BF02574025\">10.1007/BF02574025</a>."},"abstract":[{"text":"Let S be a set of n points in ℝd . A set W is a weak ε-net for (convex ranges of)S if, for any T⊆S containing εn points, the convex hull of T intersects W. We show the existence of weak ε-nets of size {Mathematical expression}, where β2=0, β3=1, and βd ≈0.149·2d-1(d-1)!, improving a previous bound of Alon et al. Such a net can be computed effectively. We also consider two special cases: when S is a planar point set in convex position, we prove the existence of a net of size O((1/ε) log1.6(1/ε)). In the case where S consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of size O(1/ε), which improves a previous bound of Capoyleas.","lang":"eng"}],"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02574025"}],"publication":"Discrete & Computational Geometry","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","page":"1 - 15","title":"Improved bounds on weak ε-nets for convex sets","type":"journal_article","oa_version":"None","article_type":"original","article_processing_charge":"No","language":[{"iso":"eng"}],"_id":"4035","status":"public","publication_status":"published","issue":"1","date_updated":"2022-06-13T12:37:06Z","intvolume":"        13","doi":"10.1007/BF02574025"},{"date_updated":"2022-06-02T12:53:01Z","status":"public","publication_status":"published","issue":"1","scopus_import":"1","doi":"10.1007/BF02574381","intvolume":"        12","_id":"4032","language":[{"iso":"eng"}],"article_processing_charge":"No","title":"Counting triangle crossings and halving planes","article_type":"original","type":"journal_article","oa_version":"None","page":"281 - 289","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","abstract":[{"text":"Every collection of t≥2 n2 triangles with a total of n vertices in ℝ3 has Ω(t4/n6) crossing pairs. This implies that one of their edges meets Ω(t3/n6) of the triangles. From this it follows that n points in ℝ3 have only O(n8/3) halving planes.","lang":"eng"}],"citation":{"ista":"Dey T, Edelsbrunner H. 1994. Counting triangle crossings and halving planes. Discrete &#38; Computational Geometry. 12(1), 281–289.","ama":"Dey T, Edelsbrunner H. Counting triangle crossings and halving planes. <i>Discrete &#38; Computational Geometry</i>. 1994;12(1):281-289. doi:<a href=\"https://doi.org/10.1007/BF02574381\">10.1007/BF02574381</a>","mla":"Dey, Tamal, and Herbert Edelsbrunner. “Counting Triangle Crossings and Halving Planes.” <i>Discrete &#38; Computational Geometry</i>, vol. 12, no. 1, Springer, 1994, pp. 281–89, doi:<a href=\"https://doi.org/10.1007/BF02574381\">10.1007/BF02574381</a>.","short":"T. Dey, H. Edelsbrunner, Discrete &#38; Computational Geometry 12 (1994) 281–289.","chicago":"Dey, Tamal, and Herbert Edelsbrunner. “Counting Triangle Crossings and Halving Planes.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1994. <a href=\"https://doi.org/10.1007/BF02574381\">https://doi.org/10.1007/BF02574381</a>.","apa":"Dey, T., &#38; Edelsbrunner, H. (1994). Counting triangle crossings and halving planes. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02574381\">https://doi.org/10.1007/BF02574381</a>","ieee":"T. Dey and H. Edelsbrunner, “Counting triangle crossings and halving planes,” <i>Discrete &#38; Computational Geometry</i>, vol. 12, no. 1. Springer, pp. 281–289, 1994."},"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02574381"}],"publication":"Discrete & Computational Geometry","publist_id":"2091","date_published":"1994-09-01T00:00:00Z","acknowledgement":"The research of H. Edelsbrunner was supported by the National Science Foundation under Grant CCR-8921421 and under an Alan T. Waterman award, Grant CCR-9118874. Any opinions, findings and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the view of the National Science Foundation.","publication_identifier":{"issn":["0179-5376"]},"publisher":"Springer","volume":12,"day":"01","year":"1994","date_created":"2018-12-11T12:06:33Z","quality_controlled":"1","author":[{"first_name":"Tamal","last_name":"Dey","full_name":"Dey, Tamal"},{"last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"}],"month":"09"},{"citation":{"ista":"Edelsbrunner H, Tan T. 1993. An upper bound for conforming Delaunay triangulations. Discrete &#38; Computational Geometry. 10(1), 197–213.","ama":"Edelsbrunner H, Tan T. An upper bound for conforming Delaunay triangulations. <i>Discrete &#38; Computational Geometry</i>. 1993;10(1):197-213. doi:<a href=\"https://doi.org/10.1007/BF02573974\">10.1007/BF02573974</a>","mla":"Edelsbrunner, Herbert, and Tiow Tan. “An Upper Bound for Conforming Delaunay Triangulations.” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1, Springer, 1993, pp. 197–213, doi:<a href=\"https://doi.org/10.1007/BF02573974\">10.1007/BF02573974</a>.","chicago":"Edelsbrunner, Herbert, and Tiow Tan. “An Upper Bound for Conforming Delaunay Triangulations.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1993. <a href=\"https://doi.org/10.1007/BF02573974\">https://doi.org/10.1007/BF02573974</a>.","short":"H. Edelsbrunner, T. Tan, Discrete &#38; Computational Geometry 10 (1993) 197–213.","apa":"Edelsbrunner, H., &#38; Tan, T. (1993). An upper bound for conforming Delaunay triangulations. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02573974\">https://doi.org/10.1007/BF02573974</a>","ieee":"H. Edelsbrunner and T. Tan, “An upper bound for conforming Delaunay triangulations,” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1. Springer, pp. 197–213, 1993."},"abstract":[{"lang":"eng","text":"A plane geometric graph C in ℝ2 conforms to another such graph G if each edge of G is the union of some edges of C. It is proved that, for every G with n vertices and m edges, there is a completion of a Delaunay triangulation of O(m2 n) points that conforms to G. The algorithm that constructs the points is also described."}],"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02573974"}],"publication":"Discrete & Computational Geometry","date_published":"1993-12-01T00:00:00Z","acknowledgement":"Research of the first author is supported by the National Science Foundation under Grant CCR-8921421 and under the Alan T. Waterman award, Grant CCR-9118874. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the view of the National Science Foundation. Work of the second author was conducted while he was on study leave at the University of Illinois. ","publication_identifier":{"issn":["0179-5376"]},"publist_id":"2084","publisher":"Springer","volume":10,"date_created":"2018-12-11T12:06:35Z","day":"01","year":"1993","month":"12","quality_controlled":"1","author":[{"full_name":"Edelsbrunner, Herbert","first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833"},{"last_name":"Tan","first_name":"Tiow","full_name":"Tan, Tiow"}],"status":"public","publication_status":"published","issue":"1","date_updated":"2022-03-28T14:58:16Z","intvolume":"        10","doi":"10.1007/BF02573974","language":[{"iso":"eng"}],"article_processing_charge":"No","_id":"4040","title":"An upper bound for conforming Delaunay triangulations","type":"journal_article","oa_version":"None","article_type":"original","extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","page":"197 - 213"},{"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02573962"}],"publication":"Discrete & Computational Geometry","citation":{"ieee":"M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, and T. Tan, “Edge insertion for optimal triangulations,” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1. Springer, pp. 47–65, 1993.","apa":"Bern, M., Edelsbrunner, H., Eppstein, D., Mitchell, S., &#38; Tan, T. (1993). Edge insertion for optimal triangulations. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02573962\">https://doi.org/10.1007/BF02573962</a>","chicago":"Bern, Marshall, Herbert Edelsbrunner, David Eppstein, Stephen Mitchell, and Tiow Tan. “Edge Insertion for Optimal Triangulations.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1993. <a href=\"https://doi.org/10.1007/BF02573962\">https://doi.org/10.1007/BF02573962</a>.","short":"M. Bern, H. Edelsbrunner, D. Eppstein, S. Mitchell, T. Tan, Discrete &#38; Computational Geometry 10 (1993) 47–65.","mla":"Bern, Marshall, et al. “Edge Insertion for Optimal Triangulations.” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1, Springer, 1993, pp. 47–65, doi:<a href=\"https://doi.org/10.1007/BF02573962\">10.1007/BF02573962</a>.","ama":"Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. Edge insertion for optimal triangulations. <i>Discrete &#38; Computational Geometry</i>. 1993;10(1):47-65. doi:<a href=\"https://doi.org/10.1007/BF02573962\">10.1007/BF02573962</a>","ista":"Bern M, Edelsbrunner H, Eppstein D, Mitchell S, Tan T. 1993. Edge insertion for optimal triangulations. Discrete &#38; Computational Geometry. 10(1), 47–65."},"abstract":[{"lang":"eng","text":"Edge insertion iteratively improves a triangulation of a finite point set in ℜ2 by adding a new edge, deleting old edges crossing the new edge, and retriangulating the polygonal regions on either side of the new edge. This paper presents an abstract view of the edge insertion paradigm, and then shows that it gives polynomial-time algorithms for several types of optimal triangulations, including minimizing the maximum slope of a piecewise-linear interpolating surface."}],"publisher":"Springer","acknowledgement":"The authors thank two anonymous referees for suggestions on improving the style of this paper. The research of the second' author was supported by the National Science Foundation under Grant No. CCR-8921421 and under the Alan T. Waterman award, Grant No. CCR-9118874. Any opinions, findings, and conclusions or recommendations expressed in this publication are those of the authors and do not necessarily reflect the view of the National Science Foundation. Part of the work was done while the second, third, and fourth authors visited the Xerox Palo Alto Research Center,\r\nand while the fifth author was on study leave at the University of Illinois. ","date_published":"1993-12-01T00:00:00Z","publication_identifier":{"issn":["0179-5376"]},"publist_id":"2082","date_created":"2018-12-11T12:06:36Z","day":"01","year":"1993","volume":10,"month":"12","quality_controlled":"1","author":[{"first_name":"Marshall","last_name":"Bern","full_name":"Bern, Marshall"},{"full_name":"Edelsbrunner, Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","first_name":"Herbert","last_name":"Edelsbrunner"},{"full_name":"Eppstein, David","last_name":"Eppstein","first_name":"David"},{"full_name":"Mitchell, Stephen","last_name":"Mitchell","first_name":"Stephen"},{"full_name":"Tan, Tiow","first_name":"Tiow","last_name":"Tan"}],"intvolume":"        10","doi":"10.1007/BF02573962","scopus_import":"1","status":"public","publication_status":"published","issue":"1","date_updated":"2022-03-28T14:10:59Z","article_processing_charge":"No","language":[{"iso":"eng"}],"_id":"4044","type":"journal_article","oa_version":"None","article_type":"original","title":"Edge insertion for optimal triangulations","extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","page":"47 - 65"},{"article_processing_charge":"No","language":[{"iso":"eng"}],"_id":"4045","issue":"1","publication_status":"published","status":"public","date_updated":"2022-03-28T14:50:42Z","intvolume":"        10","doi":"10.1007/BF02573973","scopus_import":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","extern":"1","page":"183 - 196","title":"Diameter, width, closest line pair, and parametric searching","oa_version":"None","type":"journal_article","article_type":"original","publication_identifier":{"issn":["0179-5376"]},"acknowledgement":"*Work by Bernard Chazelle was supported by NSF Grant CCR-90-02352. Work by Herbert Edelsbrunner was supported by NSF Grant CCR-89-21421. Work by Leonidas Guibas and Micha Sharir was supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Micha Sharir was also supported by ONR Grant N00014-90-J-1284, by NSF Grant CCR-89-01484, and by grants from the Fund for Basic Research administered by the Israeli Academy of Sciences, and the G.I.F., the German-Israeli Foundation for Scientific Research and Development.","date_published":"1993-12-01T00:00:00Z","publist_id":"2083","publisher":"Springer","citation":{"ama":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M. Diameter, width, closest line pair, and parametric searching. <i>Discrete &#38; Computational Geometry</i>. 1993;10(1):183-196. doi:<a href=\"https://doi.org/10.1007/BF02573973\">10.1007/BF02573973</a>","mla":"Chazelle, Bernard, et al. “Diameter, Width, Closest Line Pair, and Parametric Searching.” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1, Springer, 1993, pp. 183–96, doi:<a href=\"https://doi.org/10.1007/BF02573973\">10.1007/BF02573973</a>.","ista":"Chazelle B, Edelsbrunner H, Guibas L, Sharir M. 1993. Diameter, width, closest line pair, and parametric searching. Discrete &#38; Computational Geometry. 10(1), 183–196.","ieee":"B. Chazelle, H. Edelsbrunner, L. Guibas, and M. Sharir, “Diameter, width, closest line pair, and parametric searching,” <i>Discrete &#38; Computational Geometry</i>, vol. 10, no. 1. Springer, pp. 183–196, 1993.","short":"B. Chazelle, H. Edelsbrunner, L. Guibas, M. Sharir, Discrete &#38; Computational Geometry 10 (1993) 183–196.","chicago":"Chazelle, Bernard, Herbert Edelsbrunner, Leonidas Guibas, and Micha Sharir. “Diameter, Width, Closest Line Pair, and Parametric Searching.” <i>Discrete &#38; Computational Geometry</i>. Springer, 1993. <a href=\"https://doi.org/10.1007/BF02573973\">https://doi.org/10.1007/BF02573973</a>.","apa":"Chazelle, B., Edelsbrunner, H., Guibas, L., &#38; Sharir, M. (1993). Diameter, width, closest line pair, and parametric searching. <i>Discrete &#38; Computational Geometry</i>. Springer. <a href=\"https://doi.org/10.1007/BF02573973\">https://doi.org/10.1007/BF02573973</a>"},"abstract":[{"lang":"eng","text":"We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε&gt;0, an O(n1+ε) algorithm for computing the diameter of a point set in 3-space, an O(8/5+ε) algorithm for computing the width of such a set, and on O(n8/5+ε) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic."}],"publication":"Discrete & Computational Geometry","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02573973"}],"month":"12","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"},{"last_name":"Guibas","first_name":"Leonidas","full_name":"Guibas, Leonidas"},{"full_name":"Sharir, Micha","last_name":"Sharir","first_name":"Micha"}],"quality_controlled":"1","volume":10,"date_created":"2018-12-11T12:06:37Z","year":"1993","day":"01"},{"extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17","page":"407 - 422","oa_version":"Published Version","type":"journal_article","article_type":"original","title":"Euclidean minimum spanning trees and bichromatic closest pairs","language":[{"iso":"eng"}],"article_processing_charge":"No","_id":"4061","intvolume":"         6","scopus_import":"1","doi":"10.1007/BF02574698","publication_status":"published","issue":"1","status":"public","date_updated":"2022-02-24T15:06:41Z","month":"12","author":[{"full_name":"Agarwal, Pankaj","first_name":"Pankaj","last_name":"Agarwal"},{"full_name":"Edelsbrunner, Herbert","last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87"},{"full_name":"Schwarzkopf, Otfried","last_name":"Schwarzkopf","first_name":"Otfried"},{"last_name":"Welzl","first_name":"Emo","full_name":"Welzl, Emo"}],"quality_controlled":"1","oa":1,"date_created":"2018-12-11T12:06:42Z","year":"1991","day":"01","volume":6,"publisher":"Springer","publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"date_published":"1991-12-01T00:00:00Z","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).","publist_id":"2062","publication":"Discrete & Computational Geometry","main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02574698","open_access":"1"}],"citation":{"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.","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>.","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>","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>","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>.","short":"P. Agarwal, H. Edelsbrunner, O. Schwarzkopf, E. Welzl, Discrete &#38; Computational Geometry 6 (1991) 407–422.","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."},"abstract":[{"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}.","lang":"eng"}]},{"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"}],"citation":{"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.","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>.","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>.","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>","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."},"main_file_link":[{"url":"https://link.springer.com/article/10.1007/BF02574700","open_access":"1"}],"publication":"Discrete & Computational Geometry","publist_id":"2063","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","publication_identifier":{"issn":["0179-5376"],"eissn":["1432-0444"]},"publisher":"Springer","volume":6,"day":"01","year":"1991","date_created":"2018-12-11T12:06:43Z","oa":1,"quality_controlled":"1","author":[{"last_name":"Aronov","first_name":"Boris","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"},{"first_name":"Leonidas","last_name":"Guibas","full_name":"Guibas, Leonidas"},{"first_name":"Micha","last_name":"Sharir","full_name":"Sharir, Micha"},{"first_name":"Rephael","last_name":"Wenger","full_name":"Wenger, Rephael"}],"month":"12","date_updated":"2022-02-24T15:39:25Z","status":"public","publication_status":"published","issue":"1","scopus_import":"1","doi":"10.1007/BF02574700","intvolume":"         6","_id":"4062","article_processing_charge":"No","language":[{"iso":"eng"}],"title":"Points and triangles in the plane and halving planes in space","article_type":"original","type":"journal_article","oa_version":"Published Version","page":"435 - 442","extern":"1","user_id":"ea97e931-d5af-11eb-85d4-e6957dddbf17"}]