[{"year":"2023","acknowledgement":"We thank the anonymous reviewers for many helpful comments and suggestions, which led to substantial improvements of the paper. The first two authors were supported by the Austrian Science Fund (FWF) grant number P 29984-N35 and W1230. The first author was partly supported by an Austrian Marshall Plan Scholarship, and by the Brummer & Partners MathDataLab. A conference version of this paper was presented at the 37th International Symposium on Computational Geometry (SoCG 2021). Open access funding provided by the Royal Institute of Technology.","publisher":"Springer Nature","department":[{"_id":"HeEd"}],"publication_status":"published","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"9605"}]},"author":[{"first_name":"René","last_name":"Corbet","full_name":"Corbet, René"},{"full_name":"Kerber, Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","last_name":"Kerber","first_name":"Michael"},{"full_name":"Lesnick, Michael","last_name":"Lesnick","first_name":"Michael"},{"full_name":"Osang, Georg F","last_name":"Osang","first_name":"Georg F","orcid":"0000-0002-8882-5116","id":"464B40D6-F248-11E8-B48F-1D18A9856A87"}],"volume":70,"date_updated":"2023-10-04T12:03:40Z","date_created":"2023-03-05T23:01:06Z","file_date_updated":"2023-03-07T14:40:14Z","external_id":{"arxiv":["2103.07823"],"isi":["000936496800001"]},"tmp":{"name":"Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)","legal_code_url":"https://creativecommons.org/licenses/by/4.0/legalcode","short":"CC BY (4.0)","image":"/images/cc_by.png"},"oa":1,"isi":1,"quality_controlled":"1","doi":"10.1007/s00454-022-00476-8","language":[{"iso":"eng"}],"publication_identifier":{"eissn":["1432-0444"],"issn":["0179-5376"]},"month":"09","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"12709","intvolume":" 70","status":"public","ddc":["000"],"title":"Computing the multicover bifiltration","file":[{"date_created":"2023-03-07T14:40:14Z","date_updated":"2023-03-07T14:40:14Z","checksum":"71ce7e59f7ee4620acc704fecca620c2","success":1,"relation":"main_file","file_id":"12715","content_type":"application/pdf","file_size":1359323,"creator":"cchlebak","file_name":"2023_DisCompGeo_Corbet.pdf","access_level":"open_access"}],"oa_version":"Published Version","type":"journal_article","abstract":[{"text":"Given a finite set A ⊂ ℝ^d, let Cov_{r,k} denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called the multicover bifiltration. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors as well. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.","lang":"eng"}],"citation":{"ama":"Corbet R, Kerber M, Lesnick M, Osang GF. Computing the multicover bifiltration. Discrete and Computational Geometry. 2023;70:376-405. doi:10.1007/s00454-022-00476-8","ieee":"R. Corbet, M. Kerber, M. Lesnick, and G. F. Osang, “Computing the multicover bifiltration,” Discrete and Computational Geometry, vol. 70. Springer Nature, pp. 376–405, 2023.","apa":"Corbet, R., Kerber, M., Lesnick, M., & Osang, G. F. (2023). Computing the multicover bifiltration. Discrete and Computational Geometry. Springer Nature. https://doi.org/10.1007/s00454-022-00476-8","ista":"Corbet R, Kerber M, Lesnick M, Osang GF. 2023. Computing the multicover bifiltration. Discrete and Computational Geometry. 70, 376–405.","short":"R. Corbet, M. Kerber, M. Lesnick, G.F. Osang, Discrete and Computational Geometry 70 (2023) 376–405.","mla":"Corbet, René, et al. “Computing the Multicover Bifiltration.” Discrete and Computational Geometry, vol. 70, Springer Nature, 2023, pp. 376–405, doi:10.1007/s00454-022-00476-8.","chicago":"Corbet, René, Michael Kerber, Michael Lesnick, and Georg F Osang. “Computing the Multicover Bifiltration.” Discrete and Computational Geometry. Springer Nature, 2023. https://doi.org/10.1007/s00454-022-00476-8."},"publication":"Discrete and Computational Geometry","page":"376-405","article_type":"original","date_published":"2023-09-01T00:00:00Z","scopus_import":"1","article_processing_charge":"Yes (via OA deal)","has_accepted_license":"1","day":"01"},{"oa":1,"quality_controlled":"1","doi":"10.1137/1.9781611972931.6","conference":{"end_date":"2013-01-07","location":"New Orleans, LA, United States","start_date":"2013-01-07","name":"ALENEX: Algorithm Engineering and Experiments"},"language":[{"iso":"eng"}],"month":"01","year":"2013","publisher":"Society of Industrial and Applied Mathematics","department":[{"_id":"HeEd"}],"publication_status":"published","author":[{"first_name":"Michael","last_name":"Kerber","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299","full_name":"Kerber, Michael"},{"first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"}],"date_created":"2018-12-11T12:00:16Z","date_updated":"2021-01-12T07:00:36Z","publist_id":"3841","file_date_updated":"2020-07-14T12:45:52Z","citation":{"ama":"Kerber M, Edelsbrunner H. 3D kinetic alpha complexes and their implementation. In: 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments. Society of Industrial and Applied Mathematics; 2013:70-77. doi:10.1137/1.9781611972931.6","ista":"Kerber M, Edelsbrunner H. 2013. 3D kinetic alpha complexes and their implementation. 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments. ALENEX: Algorithm Engineering and Experiments, ALENEX, , 70–77.","ieee":"M. Kerber and H. Edelsbrunner, “3D kinetic alpha complexes and their implementation,” in 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments, New Orleans, LA, United States, 2013, pp. 70–77.","apa":"Kerber, M., & Edelsbrunner, H. (2013). 3D kinetic alpha complexes and their implementation. In 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments (pp. 70–77). New Orleans, LA, United States: Society of Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611972931.6","mla":"Kerber, Michael, and Herbert Edelsbrunner. “3D Kinetic Alpha Complexes and Their Implementation.” 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments, Society of Industrial and Applied Mathematics, 2013, pp. 70–77, doi:10.1137/1.9781611972931.6.","short":"M. Kerber, H. Edelsbrunner, in:, 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments, Society of Industrial and Applied Mathematics, 2013, pp. 70–77.","chicago":"Kerber, Michael, and Herbert Edelsbrunner. “3D Kinetic Alpha Complexes and Their Implementation.” In 2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments, 70–77. Society of Industrial and Applied Mathematics, 2013. https://doi.org/10.1137/1.9781611972931.6."},"publication":"2013 Proceedings of the 15th Workshop on Algorithm Engineering and Experiments","page":"70 - 77","date_published":"2013-01-01T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"01","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","_id":"2906","status":"public","title":"3D kinetic alpha complexes and their implementation","ddc":["500"],"pubrep_id":"547","file":[{"date_created":"2018-12-12T10:08:57Z","date_updated":"2020-07-14T12:45:52Z","checksum":"a15a3ba22df9445731507f3e06c9fcee","relation":"main_file","file_id":"4720","content_type":"application/pdf","file_size":403013,"creator":"system","file_name":"IST-2016-547-v1+1_2013-P-08-MedusaII.pdf","access_level":"open_access"}],"oa_version":"Submitted Version","type":"conference","alternative_title":["ALENEX"],"abstract":[{"text":"Motivated by an application in cell biology, we describe an extension of the kinetic data structures framework from Delaunay triangulations to fixed-radius alpha complexes. Our algorithm is implemented\r\nusing CGAL, following the exact geometric computation paradigm. We report on several\r\ntechniques to accelerate the computation that turn our implementation applicable to the underlying biological\r\nproblem.","lang":"eng"}]},{"doi":"10.1016/j.comgeo.2012.02.010","date_published":"2013-05-01T00:00:00Z","language":[{"iso":"eng"}],"publication":"Computational Geometry: Theory and Applications","citation":{"chicago":"Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent Homology.” Computational Geometry: Theory and Applications. Elsevier, 2013. https://doi.org/10.1016/j.comgeo.2012.02.010.","short":"C. Chen, M. Kerber, Computational Geometry: Theory and Applications 46 (2013) 435–447.","mla":"Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent Homology.” Computational Geometry: Theory and Applications, vol. 46, no. 4, Elsevier, 2013, pp. 435–47, doi:10.1016/j.comgeo.2012.02.010.","apa":"Chen, C., & Kerber, M. (2013). An output sensitive algorithm for persistent homology. Computational Geometry: Theory and Applications. Elsevier. https://doi.org/10.1016/j.comgeo.2012.02.010","ieee":"C. Chen and M. Kerber, “An output sensitive algorithm for persistent homology,” Computational Geometry: Theory and Applications, vol. 46, no. 4. Elsevier, pp. 435–447, 2013.","ista":"Chen C, Kerber M. 2013. An output sensitive algorithm for persistent homology. Computational Geometry: Theory and Applications. 46(4), 435–447.","ama":"Chen C, Kerber M. An output sensitive algorithm for persistent homology. Computational Geometry: Theory and Applications. 2013;46(4):435-447. doi:10.1016/j.comgeo.2012.02.010"},"quality_controlled":"1","page":"435 - 447","day":"01","month":"05","scopus_import":1,"author":[{"full_name":"Chen, Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","last_name":"Chen","first_name":"Chao"},{"full_name":"Kerber, Michael","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299","first_name":"Michael","last_name":"Kerber"}],"related_material":{"record":[{"status":"public","relation":"earlier_version","id":"3367"}]},"date_updated":"2023-02-23T11:24:10Z","date_created":"2018-12-11T12:00:27Z","volume":46,"oa_version":"None","acknowledgement":"The authors thank Herbert Edelsbrunner for many helpful discussions and suggestions. Moreover, they are grateful for the careful reviews that helped to improve the quality of the paper.","_id":"2939","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","year":"2013","status":"public","publication_status":"published","title":"An output sensitive algorithm for persistent homology","intvolume":" 46","department":[{"_id":"HeEd"}],"publisher":"Elsevier","abstract":[{"lang":"eng","text":"In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ > 0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0, 1), the running time is O (C (1 - δ) Γ R d (n) log n), where C (1 - δ) Γ is the number of homology classes with persistence at least (1 - δ) Γ, n is the total number of simplices in the complex, d its dimension, and R d (n) is the complexity of computing the rank of an n × n matrix with O (d n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O (C (1 - δ) Γ n 2.376) algorithm, an O (C (1 - δ) Γ n 2.28) Las-Vegas algorithm, or an O (C (1 - δ) Γ n 2 + ε{lunate}) Monte-Carlo algorithm for an arbitrary ε{lunate} > 0. The space complexity of the Monte-Carlo version is bounded by O (d n) = O (n log n)."}],"issue":"4","publist_id":"3796","type":"journal_article"},{"day":"01","scopus_import":1,"date_published":"2012-07-01T00:00:00Z","citation":{"ama":"Brown G, Kerber M, Reid M. Fano 3 folds in codimension 4 Tom and Jerry Part I. Compositio Mathematica. 2012;148(4):1171-1194. doi:10.1112/S0010437X11007226","ista":"Brown G, Kerber M, Reid M. 2012. Fano 3 folds in codimension 4 Tom and Jerry Part I. Compositio Mathematica. 148(4), 1171–1194.","ieee":"G. Brown, M. Kerber, and M. Reid, “Fano 3 folds in codimension 4 Tom and Jerry Part I,” Compositio Mathematica, vol. 148, no. 4. Cambridge University Press, pp. 1171–1194, 2012.","apa":"Brown, G., Kerber, M., & Reid, M. (2012). Fano 3 folds in codimension 4 Tom and Jerry Part I. Compositio Mathematica. Cambridge University Press. https://doi.org/10.1112/S0010437X11007226","mla":"Brown, Gavin, et al. “Fano 3 Folds in Codimension 4 Tom and Jerry Part I.” Compositio Mathematica, vol. 148, no. 4, Cambridge University Press, 2012, pp. 1171–94, doi:10.1112/S0010437X11007226.","short":"G. Brown, M. Kerber, M. Reid, Compositio Mathematica 148 (2012) 1171–1194.","chicago":"Brown, Gavin, Michael Kerber, and Miles Reid. “Fano 3 Folds in Codimension 4 Tom and Jerry Part I.” Compositio Mathematica. Cambridge University Press, 2012. https://doi.org/10.1112/S0010437X11007226."},"publication":"Compositio Mathematica","page":"1171 - 1194","issue":"4","abstract":[{"text":"We introduce a strategy based on Kustin-Miller unprojection that allows us to construct many hundreds of Gorenstein codimension 4 ideals with 9 × 16 resolutions (that is, nine equations and sixteen first syzygies). Our two basic games are called Tom and Jerry; the main application is the biregular construction of most of the anticanonically polarised Mori Fano 3-folds of Altinok's thesis. There are 115 cases whose numerical data (in effect, the Hilbert series) allow a Type I projection. In every case, at least one Tom and one Jerry construction works, providing at least two deformation families of quasismooth Fano 3-folds having the same numerics but different topology. © 2012 Copyright Foundation Compositio Mathematica.","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"3120","intvolume":" 148","status":"public","title":"Fano 3 folds in codimension 4 Tom and Jerry Part I","month":"07","doi":"10.1112/S0010437X11007226","language":[{"iso":"eng"}],"oa":1,"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1009.4313"}],"quality_controlled":"1","publist_id":"3579","author":[{"full_name":"Brown, Gavin","first_name":"Gavin","last_name":"Brown"},{"full_name":"Kerber, Michael","last_name":"Kerber","first_name":"Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Reid","first_name":"Miles","full_name":"Reid, Miles"}],"volume":148,"date_updated":"2021-01-12T07:41:12Z","date_created":"2018-12-11T12:01:30Z","acknowledgement":"This research is supported by the Korean Government WCU Grant R33-2008-000-10101-0.","year":"2012","department":[{"_id":"HeEd"}],"publisher":"Cambridge University Press","publication_status":"published"},{"scopus_import":1,"month":"06","day":"20","oa":1,"citation":{"ieee":"H. Edelsbrunner and M. Kerber, “Alexander duality for functions: The persistent behavior of land and water and shore,” in Proceedings of the twenty-eighth annual symposium on Computational geometry , Chapel Hill, NC, USA, 2012, pp. 249–258.","apa":"Edelsbrunner, H., & Kerber, M. (2012). Alexander duality for functions: The persistent behavior of land and water and shore. In Proceedings of the twenty-eighth annual symposium on Computational geometry (pp. 249–258). Chapel Hill, NC, USA: ACM. https://doi.org/10.1145/2261250.2261287","ista":"Edelsbrunner H, Kerber M. 2012. Alexander duality for functions: The persistent behavior of land and water and shore. Proceedings of the twenty-eighth annual symposium on Computational geometry . SCG: Symposium on Computational Geometry, 249–258.","ama":"Edelsbrunner H, Kerber M. Alexander duality for functions: The persistent behavior of land and water and shore. In: Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry . ACM; 2012:249-258. doi:10.1145/2261250.2261287","chicago":"Edelsbrunner, Herbert, and Michael Kerber. “Alexander Duality for Functions: The Persistent Behavior of Land and Water and Shore.” In Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry , 249–58. ACM, 2012. https://doi.org/10.1145/2261250.2261287.","short":"H. Edelsbrunner, M. Kerber, in:, Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry , ACM, 2012, pp. 249–258.","mla":"Edelsbrunner, Herbert, and Michael Kerber. “Alexander Duality for Functions: The Persistent Behavior of Land and Water and Shore.” Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry , ACM, 2012, pp. 249–58, doi:10.1145/2261250.2261287."},"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1109.5052"}],"publication":"Proceedings of the twenty-eighth annual symposium on Computational geometry ","page":"249 - 258","quality_controlled":"1","doi":"10.1145/2261250.2261287","date_published":"2012-06-20T00:00:00Z","conference":{"name":"SCG: Symposium on Computational Geometry","start_date":"2012-06-17","location":"Chapel Hill, NC, USA","end_date":"2012-06-20"},"language":[{"iso":"eng"}],"type":"conference","publist_id":"3564","abstract":[{"text":"This note contributes to the point calculus of persistent homology by extending Alexander duality from spaces to real-valued functions. Given a perfect Morse function f: S n+1 →[0, 1 and a decomposition S n+1 = U ∪ V into two (n + 1)-manifolds with common boundary M, we prove elementary relationships between the persistence diagrams of f restricted to U, to V, and to M. ","lang":"eng"}],"user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"3133","acknowledgement":"his research is partially supported by the National Science Foundation (NSF) under grant DBI-0820624, the European Science Foundation under the Research Networking Programme, and the Russian Government Project 11.G34.31.0053.\r\nThe authors thank an anonymous referee for suggesting the simplified proof of the Contravariant PE Theorem given in this paper. They also thank Frederick Cohen, Yuriy Mileyko and Amit Patel for helpful discussions.","year":"2012","department":[{"_id":"HeEd"}],"publisher":"ACM","title":"Alexander duality for functions: The persistent behavior of land and water and shore","status":"public","publication_status":"published","author":[{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","last_name":"Kerber","first_name":"Michael","full_name":"Kerber, Michael"}],"oa_version":"Preprint","date_created":"2018-12-11T12:01:35Z","date_updated":"2021-01-12T07:41:17Z"},{"citation":{"chicago":"Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions of ℝn.” Discrete & Computational Geometry. Springer, 2012. https://doi.org/10.1007/s00454-011-9382-4.","short":"H. Edelsbrunner, M. Kerber, Discrete & Computational Geometry 47 (2012) 393–414.","mla":"Edelsbrunner, Herbert, and Michael Kerber. “Dual Complexes of Cubical Subdivisions of ℝn.” Discrete & Computational Geometry, vol. 47, no. 2, Springer, 2012, pp. 393–414, doi:10.1007/s00454-011-9382-4.","apa":"Edelsbrunner, H., & Kerber, M. (2012). Dual complexes of cubical subdivisions of ℝn. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-011-9382-4","ieee":"H. Edelsbrunner and M. Kerber, “Dual complexes of cubical subdivisions of ℝn,” Discrete & Computational Geometry, vol. 47, no. 2. Springer, pp. 393–414, 2012.","ista":"Edelsbrunner H, Kerber M. 2012. Dual complexes of cubical subdivisions of ℝn. Discrete & Computational Geometry. 47(2), 393–414.","ama":"Edelsbrunner H, Kerber M. Dual complexes of cubical subdivisions of ℝn. Discrete & Computational Geometry. 2012;47(2):393-414. doi:10.1007/s00454-011-9382-4"},"publication":"Discrete & Computational Geometry","page":"393 - 414","date_published":"2012-03-01T00:00:00Z","scopus_import":1,"has_accepted_license":"1","day":"01","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","_id":"3256","intvolume":" 47","status":"public","ddc":["000"],"title":"Dual complexes of cubical subdivisions of ℝn","pubrep_id":"543","oa_version":"Submitted Version","file":[{"checksum":"76486f3b2c9e7fd81342f3832ca387e7","date_updated":"2020-07-14T12:46:05Z","date_created":"2018-12-12T10:08:15Z","relation":"main_file","file_id":"4675","file_size":203636,"content_type":"application/pdf","creator":"system","access_level":"open_access","file_name":"IST-2016-543-v1+1_2012-J-08-HierarchyCubeComplex.pdf"}],"type":"journal_article","issue":"2","abstract":[{"text":"We use a distortion to define the dual complex of a cubical subdivision of ℝ n as an n-dimensional subcomplex of the nerve of the set of n-cubes. Motivated by the topological analysis of high-dimensional digital image data, we consider such subdivisions defined by generalizations of quad- and oct-trees to n dimensions. Assuming the subdivision is balanced, we show that mapping each vertex to the center of the corresponding n-cube gives a geometric realization of the dual complex in ℝ n.","lang":"eng"}],"oa":1,"quality_controlled":"1","doi":"10.1007/s00454-011-9382-4","language":[{"iso":"eng"}],"month":"03","year":"2012","acknowledgement":"This research is partially supported by the Defense Advanced Research Projects Agency (DARPA) under grants HR0011-05-1-0057 and HR0011-09-0065 as well as the National Science Foundation (NSF) under grant DBI-0820624.","department":[{"_id":"HeEd"}],"publisher":"Springer","publication_status":"published","author":[{"orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","last_name":"Edelsbrunner","first_name":"Herbert","full_name":"Edelsbrunner, Herbert"},{"last_name":"Kerber","first_name":"Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","full_name":"Kerber, Michael"}],"volume":47,"date_updated":"2021-01-12T07:42:10Z","date_created":"2018-12-11T12:02:17Z","publist_id":"3398","file_date_updated":"2020-07-14T12:46:05Z"},{"publist_id":"3584","related_material":{"record":[{"status":"public","relation":"earlier_version","id":"3329"}]},"author":[{"full_name":"Berberich, Eric","first_name":"Eric","last_name":"Berberich"},{"full_name":"Halperin, Dan","last_name":"Halperin","first_name":"Dan"},{"first_name":"Michael","last_name":"Kerber","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299","full_name":"Kerber, Michael"},{"full_name":"Pogalnikova, Roza","last_name":"Pogalnikova","first_name":"Roza"}],"volume":48,"date_updated":"2023-02-23T11:22:30Z","date_created":"2018-12-11T12:01:28Z","year":"2012","acknowledgement":"We thank Eyal Flato (Plataine Ltd.) for raising the offset-deconstruction problem in connection with wood cutting. We also thank Tim Bretl (UIUC) for suggesting the digital-pen offset-deconstruction problem. This work has been supported in part by the Israel Science Foundation (grant no. 1102/11), by the German–Israeli Foundation (grant no. 969/07), by the Hermann Minkowski–Minerva Center for Geometry at Tel Aviv University, and by the EU Project under Contract No. 255827 (CGL—Computational Geometry Learning).\r\n","publisher":"Springer","department":[{"_id":"HeEd"}],"publication_status":"published","month":"12","doi":"10.1007/s00454-012-9441-5","language":[{"iso":"eng"}],"external_id":{"arxiv":["1109.2158"]},"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1109.2158"}],"oa":1,"quality_controlled":"1","issue":"4","abstract":[{"text":"We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance ε in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(nlogn)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. A variant of the algorithm, which we have implemented using the cgal library, is based on rational arithmetic and answers the same deconstruction problem up to an uncertainty parameter δ its running time additionally depends on δ. If the input shape is found to be approximable, this algorithm also computes an approximate solution for the problem. It also allows us to solve parameter-optimization problems induced by the offset-deconstruction problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution P with at most one more vertex than a vertex-minimal one.","lang":"eng"}],"type":"journal_article","oa_version":"Preprint","_id":"3115","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","intvolume":" 48","title":"Deconstructing approximate offsets","status":"public","day":"01","scopus_import":1,"date_published":"2012-12-01T00:00:00Z","citation":{"chicago":"Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing Approximate Offsets.” Discrete & Computational Geometry. Springer, 2012. https://doi.org/10.1007/s00454-012-9441-5.","short":"E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, Discrete & Computational Geometry 48 (2012) 964–989.","mla":"Berberich, Eric, et al. “Deconstructing Approximate Offsets.” Discrete & Computational Geometry, vol. 48, no. 4, Springer, 2012, pp. 964–89, doi:10.1007/s00454-012-9441-5.","ieee":"E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing approximate offsets,” Discrete & Computational Geometry, vol. 48, no. 4. Springer, pp. 964–989, 2012.","apa":"Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2012). Deconstructing approximate offsets. Discrete & Computational Geometry. Springer. https://doi.org/10.1007/s00454-012-9441-5","ista":"Berberich E, Halperin D, Kerber M, Pogalnikova R. 2012. Deconstructing approximate offsets. Discrete & Computational Geometry. 48(4), 964–989.","ama":"Berberich E, Halperin D, Kerber M, Pogalnikova R. Deconstructing approximate offsets. Discrete & Computational Geometry. 2012;48(4):964-989. doi:10.1007/s00454-012-9441-5"},"publication":"Discrete & Computational Geometry","page":"964 - 989"},{"language":[{"iso":"eng"}],"date_published":"2012-03-01T00:00:00Z","doi":"10.1016/j.jsc.2011.11.001","quality_controlled":"1","page":"239 - 258","publication":" Journal of Symbolic Computation","oa":1,"citation":{"mla":"Kerber, Michael, and Michael Sagraloff. “A Worst Case Bound for Topology Computation of Algebraic Curves.” Journal of Symbolic Computation, vol. 47, no. 3, Elsevier, 2012, pp. 239–58, doi:10.1016/j.jsc.2011.11.001.","short":"M. Kerber, M. Sagraloff, Journal of Symbolic Computation 47 (2012) 239–258.","chicago":"Kerber, Michael, and Michael Sagraloff. “A Worst Case Bound for Topology Computation of Algebraic Curves.” Journal of Symbolic Computation. Elsevier, 2012. https://doi.org/10.1016/j.jsc.2011.11.001.","ama":"Kerber M, Sagraloff M. A worst case bound for topology computation of algebraic curves. Journal of Symbolic Computation. 2012;47(3):239-258. doi:10.1016/j.jsc.2011.11.001","ista":"Kerber M, Sagraloff M. 2012. A worst case bound for topology computation of algebraic curves. Journal of Symbolic Computation. 47(3), 239–258.","ieee":"M. Kerber and M. Sagraloff, “A worst case bound for topology computation of algebraic curves,” Journal of Symbolic Computation, vol. 47, no. 3. Elsevier, pp. 239–258, 2012.","apa":"Kerber, M., & Sagraloff, M. (2012). A worst case bound for topology computation of algebraic curves. Journal of Symbolic Computation. Elsevier. https://doi.org/10.1016/j.jsc.2011.11.001"},"main_file_link":[{"open_access":"1","url":"http://arxiv.org/abs/1104.1510"}],"day":"01","month":"03","scopus_import":1,"date_created":"2018-12-11T12:02:43Z","date_updated":"2021-01-12T07:42:43Z","volume":47,"oa_version":"Preprint","author":[{"full_name":"Kerber, Michael","first_name":"Michael","last_name":"Kerber","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299"},{"first_name":"Michael","last_name":"Sagraloff","full_name":"Sagraloff, Michael"}],"status":"public","title":"A worst case bound for topology computation of algebraic curves","publication_status":"published","department":[{"_id":"HeEd"}],"intvolume":" 47","publisher":"Elsevier","_id":"3331","year":"2012","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","abstract":[{"lang":"eng","text":"Computing the topology of an algebraic plane curve C means computing a combinatorial graph that is isotopic to C and thus represents its topology in R2. We prove that, for a polynomial of degree n with integer coefficients bounded by 2ρ, the topology of the induced curve can be computed with bit operations ( indicates that we omit logarithmic factors). Our analysis improves the previous best known complexity bounds by a factor of n2. The improvement is based on new techniques to compute and refine isolating intervals for the real roots of polynomials, and on the consequent amortized analysis of the critical fibers of the algebraic curve."}],"issue":"3","publist_id":"3303","type":"journal_article"},{"publication":"Proceedings of the twenty-seventh annual symposium on Computational geometry","main_file_link":[{"url":"http://arxiv.org/abs/1109.2158","open_access":"1"}],"citation":{"ama":"Berberich E, Halperin D, Kerber M, Pogalnikova R. Deconstructing approximate offsets. In: Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry. ACM; 2011:187-196. doi:10.1145/1998196.1998225","ista":"Berberich E, Halperin D, Kerber M, Pogalnikova R. 2011. Deconstructing approximate offsets. Proceedings of the twenty-seventh annual symposium on Computational geometry. SCG: Symposium on Computational Geometry, 187–196.","apa":"Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2011). Deconstructing approximate offsets. In Proceedings of the twenty-seventh annual symposium on Computational geometry (pp. 187–196). Paris, France: ACM. https://doi.org/10.1145/1998196.1998225","ieee":"E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Deconstructing approximate offsets,” in Proceedings of the twenty-seventh annual symposium on Computational geometry, Paris, France, 2011, pp. 187–196.","mla":"Berberich, Eric, et al. “Deconstructing Approximate Offsets.” Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011, pp. 187–96, doi:10.1145/1998196.1998225.","short":"E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, ACM, 2011, pp. 187–196.","chicago":"Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Deconstructing Approximate Offsets.” In Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, 187–96. ACM, 2011. https://doi.org/10.1145/1998196.1998225."},"oa":1,"quality_controlled":"1","page":"187 - 196","conference":{"start_date":"2011-06-13","location":"Paris, France","end_date":"2011-06-15","name":"SCG: Symposium on Computational Geometry"},"date_published":"2011-06-13T00:00:00Z","doi":"10.1145/1998196.1998225","language":[{"iso":"eng"}],"scopus_import":1,"month":"06","day":"13","year":"2011","_id":"3329","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","publication_status":"published","status":"public","title":"Deconstructing approximate offsets","publisher":"ACM","department":[{"_id":"HeEd"}],"author":[{"full_name":"Berberich, Eric","first_name":"Eric","last_name":"Berberich"},{"last_name":"Halperin","first_name":"Dan","full_name":"Halperin, Dan"},{"last_name":"Kerber","first_name":"Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","full_name":"Kerber, Michael"},{"first_name":"Roza","last_name":"Pogalnikova","full_name":"Pogalnikova, Roza"}],"related_material":{"record":[{"status":"public","relation":"later_version","id":"3115"}]},"date_created":"2018-12-11T12:02:42Z","date_updated":"2023-02-23T11:12:57Z","oa_version":"Preprint","type":"conference","abstract":[{"lang":"eng","text":"We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance µ in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution shape P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. An alternative algorithm, based purely on rational arithmetic, answers the same deconstruction problem, up to an uncertainty parameter, and its running time depends on the parameter δ (in addition to the other input parameters: n, δ and the radius of the disk). If the input shape is found to be approximable, the rational-arithmetic algorithm also computes an approximate solution shape for the problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution shape P with at most one more vertex than a vertex-minimal one. Our study is motivated by applications from two different domains. However, since the offset operation has numerous uses, we anticipate that the reverse question that we study here will be still more broadly applicable. We present results obtained with our implementation of the rational-arithmetic algorithm."}],"publist_id":"3306"},{"month":"03","doi":"10.1007/s00373-011-1020-7","language":[{"iso":"eng"}],"oa":1,"quality_controlled":"1","file_date_updated":"2020-07-14T12:46:08Z","publist_id":"3301","author":[{"full_name":"Kerber, Michael","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299","first_name":"Michael","last_name":"Kerber"},{"full_name":"Sagraloff, Michael","last_name":"Sagraloff","first_name":"Michael"}],"date_updated":"2021-01-12T07:42:43Z","date_created":"2018-12-11T12:02:43Z","volume":27,"year":"2011","publication_status":"published","publisher":"Springer","department":[{"_id":"HeEd"}],"day":"17","article_processing_charge":"No","has_accepted_license":"1","scopus_import":1,"date_published":"2011-03-17T00:00:00Z","publication":"Graphs and Combinatorics","citation":{"short":"M. Kerber, M. Sagraloff, Graphs and Combinatorics 27 (2011) 419–430.","mla":"Kerber, Michael, and Michael Sagraloff. “A Note on the Complexity of Real Algebraic Hypersurfaces.” Graphs and Combinatorics, vol. 27, no. 3, Springer, 2011, pp. 419–30, doi:10.1007/s00373-011-1020-7.","chicago":"Kerber, Michael, and Michael Sagraloff. “A Note on the Complexity of Real Algebraic Hypersurfaces.” Graphs and Combinatorics. Springer, 2011. https://doi.org/10.1007/s00373-011-1020-7.","ama":"Kerber M, Sagraloff M. A note on the complexity of real algebraic hypersurfaces. Graphs and Combinatorics. 2011;27(3):419-430. doi:10.1007/s00373-011-1020-7","ieee":"M. Kerber and M. Sagraloff, “A note on the complexity of real algebraic hypersurfaces,” Graphs and Combinatorics, vol. 27, no. 3. Springer, pp. 419–430, 2011.","apa":"Kerber, M., & Sagraloff, M. (2011). A note on the complexity of real algebraic hypersurfaces. Graphs and Combinatorics. Springer. https://doi.org/10.1007/s00373-011-1020-7","ista":"Kerber M, Sagraloff M. 2011. A note on the complexity of real algebraic hypersurfaces. Graphs and Combinatorics. 27(3), 419–430."},"article_type":"original","page":"419 - 430","abstract":[{"lang":"eng","text":"Given an algebraic hypersurface O in ℝd, how many simplices are necessary for a simplicial complex isotopic to O? We address this problem and the variant where all vertices of the complex must lie on O. We give asymptotically tight worst-case bounds for algebraic plane curves. Our results gradually improve known bounds in higher dimensions; however, the question for tight bounds remains unsolved for d ≥ 3."}],"issue":"3","type":"journal_article","oa_version":"Submitted Version","file":[{"content_type":"application/pdf","file_size":143976,"creator":"dernst","file_name":"2011_GraphsCombi_Kerber.pdf","access_level":"open_access","date_created":"2020-05-19T16:11:36Z","date_updated":"2020-07-14T12:46:08Z","checksum":"a63a1e3e885dcc68f1e3dea68dfbe213","relation":"main_file","file_id":"7869"}],"_id":"3332","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","ddc":["500"],"status":"public","title":"A note on the complexity of real algebraic hypersurfaces","intvolume":" 27"},{"author":[{"full_name":"Kerber, Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","last_name":"Kerber","first_name":"Michael"},{"last_name":"Sagraloff","first_name":"Michael","full_name":"Sagraloff, Michael"}],"oa_version":"Preprint","date_created":"2018-12-11T12:02:43Z","date_updated":"2021-01-12T07:42:42Z","year":"2011","_id":"3330","user_id":"3E5EF7F0-F248-11E8-B48F-1D18A9856A87","department":[{"_id":"HeEd"}],"publisher":"Springer","status":"public","publication_status":"published","title":"Root refinement for real polynomials","publist_id":"3304","abstract":[{"text":"We consider the problem of approximating all real roots of a square-free polynomial f. Given isolating intervals, our algorithm refines each of them to a width at most 2-L, that is, each of the roots is approximated to L bits after the binary point. Our method provides a certified answer for arbitrary real polynomials, only requiring finite approximations of the polynomial coefficient and choosing a suitable working precision adaptively. In this way, we get a correct algorithm that is simple to implement and practically efficient. Our algorithm uses the quadratic interval refinement method; we adapt that method to be able to cope with inaccuracies when evaluating f, without sacrificing its quadratic convergence behavior. We prove a bound on the bit complexity of our algorithm in terms of degree, coefficient size and discriminant. Our bound improves previous work on integer polynomials by a factor of deg f and essentially matches best known theoretical bounds on root approximation which are obtained by very sophisticated algorithms.","lang":"eng"}],"type":"conference","date_published":"2011-06-08T00:00:00Z","doi":"10.1145/1993886.1993920","conference":{"name":"ISSAC: International Symposium on Symbolic and Algebraic Computation","end_date":"2011-06-11","location":"California, USA","start_date":"2011-06-08"},"language":[{"iso":"eng"}],"oa":1,"citation":{"chicago":"Kerber, Michael, and Michael Sagraloff. “Root Refinement for Real Polynomials,” 209–16. Springer, 2011. https://doi.org/10.1145/1993886.1993920.","short":"M. Kerber, M. Sagraloff, in:, Springer, 2011, pp. 209–216.","mla":"Kerber, Michael, and Michael Sagraloff. Root Refinement for Real Polynomials. Springer, 2011, pp. 209–16, doi:10.1145/1993886.1993920.","apa":"Kerber, M., & Sagraloff, M. (2011). Root refinement for real polynomials (pp. 209–216). Presented at the ISSAC: International Symposium on Symbolic and Algebraic Computation, California, USA: Springer. https://doi.org/10.1145/1993886.1993920","ieee":"M. Kerber and M. Sagraloff, “Root refinement for real polynomials,” presented at the ISSAC: International Symposium on Symbolic and Algebraic Computation, California, USA, 2011, pp. 209–216.","ista":"Kerber M, Sagraloff M. 2011. Root refinement for real polynomials. ISSAC: International Symposium on Symbolic and Algebraic Computation, 209–216.","ama":"Kerber M, Sagraloff M. Root refinement for real polynomials. In: Springer; 2011:209-216. doi:10.1145/1993886.1993920"},"main_file_link":[{"url":"http://arxiv.org/abs/1104.1362","open_access":"1"}],"external_id":{"arxiv":["1104.1362"]},"page":"209 - 216","quality_controlled":"1","article_processing_charge":"No","day":"08","month":"06","scopus_import":1},{"month":"06","day":"13","article_processing_charge":"No","scopus_import":1,"language":[{"iso":"eng"}],"conference":{"end_date":"2011-06-15","start_date":"2011-06-13","location":"Paris, France","name":"SCG: Symposium on Computational Geometry"},"date_published":"2011-06-13T00:00:00Z","doi":"10.1145/1998196.1998224","quality_controlled":"1","page":"179 - 186","citation":{"short":"E. Berberich, M. Hemmer, M. Kerber, in:, ACM, 2011, pp. 179–186.","mla":"Berberich, Eric, et al. A Generic Algebraic Kernel for Non Linear Geometric Applications. ACM, 2011, pp. 179–86, doi:10.1145/1998196.1998224.","chicago":"Berberich, Eric, Michael Hemmer, and Michael Kerber. “A Generic Algebraic Kernel for Non Linear Geometric Applications,” 179–86. ACM, 2011. https://doi.org/10.1145/1998196.1998224.","ama":"Berberich E, Hemmer M, Kerber M. A generic algebraic kernel for non linear geometric applications. In: ACM; 2011:179-186. doi:10.1145/1998196.1998224","apa":"Berberich, E., Hemmer, M., & Kerber, M. (2011). A generic algebraic kernel for non linear geometric applications (pp. 179–186). Presented at the SCG: Symposium on Computational Geometry, Paris, France: ACM. https://doi.org/10.1145/1998196.1998224","ieee":"E. Berberich, M. Hemmer, and M. Kerber, “A generic algebraic kernel for non linear geometric applications,” presented at the SCG: Symposium on Computational Geometry, Paris, France, 2011, pp. 179–186.","ista":"Berberich E, Hemmer M, Kerber M. 2011. A generic algebraic kernel for non linear geometric applications. SCG: Symposium on Computational Geometry, 179–186."},"main_file_link":[{"open_access":"1","url":"https://hal.inria.fr/inria-00480031/file/RR-7274.pdf"}],"oa":1,"abstract":[{"text":"We report on a generic uni- and bivariate algebraic kernel that is publicly available with CGAL 3.7. It comprises complete, correct, though efficient state-of-the-art implementations on polynomials, roots of polynomial systems, and the support to analyze algebraic curves defined by bivariate polynomials. The kernel design is generic, that is, various number types and substeps can be exchanged. It is accompanied with a ready-to-use interface to enable arrangements induced by algebraic curves, that have already been used as basis for various geometric applications, as arrangements on Dupin cyclides or the triangulation of algebraic surfaces. We present two novel applications: arrangements of rotated algebraic curves and Boolean set operations on polygons bounded by segments of algebraic curves. We also provide experiments showing that our general implementation is competitive and even often clearly outperforms existing implementations that are explicitly tailored for specific types of non-linear curves that are available in CGAL.","lang":"eng"}],"publist_id":"3307","type":"conference","date_created":"2018-12-11T12:02:42Z","date_updated":"2021-01-12T07:42:41Z","oa_version":"Published Version","author":[{"full_name":"Berberich, Eric","last_name":"Berberich","first_name":"Eric"},{"first_name":"Michael","last_name":"Hemmer","full_name":"Hemmer, Michael"},{"full_name":"Kerber, Michael","first_name":"Michael","last_name":"Kerber","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299"}],"status":"public","title":"A generic algebraic kernel for non linear geometric applications","publication_status":"published","publisher":"ACM","department":[{"_id":"HeEd"}],"_id":"3328","year":"2011","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87"},{"_id":"3367","year":"2011","user_id":"2DF688A6-F248-11E8-B48F-1D18A9856A87","publication_status":"published","title":"An output sensitive algorithm for persistent homology","status":"public","department":[{"_id":"HeEd"}],"publisher":"ACM","author":[{"id":"3E92416E-F248-11E8-B48F-1D18A9856A87","last_name":"Chen","first_name":"Chao","full_name":"Chen, Chao"},{"full_name":"Kerber, Michael","last_name":"Kerber","first_name":"Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87"}],"related_material":{"record":[{"relation":"later_version","status":"public","id":"2939"}]},"date_created":"2018-12-11T12:02:56Z","date_updated":"2023-02-23T11:05:04Z","oa_version":"None","type":"conference","abstract":[{"text":"In this paper, we present the first output-sensitive algorithm to compute the persistence diagram of a filtered simplicial complex. For any Γ>0, it returns only those homology classes with persistence at least Γ. Instead of the classical reduction via column operations, our algorithm performs rank computations on submatrices of the boundary matrix. For an arbitrary constant δ ∈ (0,1), the running time is O(C(1-δ)ΓR(n)log n), where C(1-δ)Γ is the number of homology classes with persistence at least (1-δ)Γ, n is the total number of simplices, and R(n) is the complexity of computing the rank of an n x n matrix with O(n) nonzero entries. Depending on the choice of the rank algorithm, this yields a deterministic O(C(1-δ)Γn2.376) algorithm, a O(C(1-δ)Γn2.28) Las-Vegas algorithm, or a O(C(1-δ)Γn2+ε) Monte-Carlo algorithm for an arbitrary ε>0.","lang":"eng"}],"publist_id":"3245","citation":{"ista":"Chen C, Kerber M. 2011. An output sensitive algorithm for persistent homology. SoCG: Symposium on Computational Geometry, 207–216.","ieee":"C. Chen and M. Kerber, “An output sensitive algorithm for persistent homology,” presented at the SoCG: Symposium on Computational Geometry, Paris, France, 2011, pp. 207–216.","apa":"Chen, C., & Kerber, M. (2011). An output sensitive algorithm for persistent homology (pp. 207–216). Presented at the SoCG: Symposium on Computational Geometry, Paris, France: ACM. https://doi.org/10.1145/1998196.1998228","ama":"Chen C, Kerber M. An output sensitive algorithm for persistent homology. In: ACM; 2011:207-216. doi:10.1145/1998196.1998228","chicago":"Chen, Chao, and Michael Kerber. “An Output Sensitive Algorithm for Persistent Homology,” 207–16. ACM, 2011. https://doi.org/10.1145/1998196.1998228.","mla":"Chen, Chao, and Michael Kerber. An Output Sensitive Algorithm for Persistent Homology. ACM, 2011, pp. 207–16, doi:10.1145/1998196.1998228.","short":"C. Chen, M. Kerber, in:, ACM, 2011, pp. 207–216."},"quality_controlled":"1","page":"207 - 216","conference":{"end_date":"2011-06-15","location":"Paris, France","start_date":"2011-06-13","name":"SoCG: Symposium on Computational Geometry"},"doi":"10.1145/1998196.1998228","date_published":"2011-06-13T00:00:00Z","language":[{"iso":"eng"}],"scopus_import":1,"day":"13","month":"06","article_processing_charge":"No"},{"month":"05","quality_controlled":"1","oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/978-3-642-19391-0_2","file_date_updated":"2020-07-14T12:46:16Z","publist_id":"2427","publication_status":"published","publisher":"Springer","editor":[{"last_name":"Calude","first_name":"Cristian","full_name":"Calude, Cristian"},{"full_name":"Rozenberg, Grzegorz","last_name":"Rozenberg","first_name":"Grzegorz"},{"full_name":"Salomaa, Arto","first_name":"Arto","last_name":"Salomaa"}],"department":[{"_id":"HeEd"}],"year":"2011","date_created":"2018-12-11T12:05:13Z","date_updated":"2021-01-12T07:52:15Z","volume":6570,"author":[{"first_name":"Herbert","last_name":"Edelsbrunner","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","full_name":"Edelsbrunner, Herbert"},{"last_name":"Kerber","first_name":"Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","full_name":"Kerber, Michael"}],"series_title":"Dedicated to Hermann Maurer on the Occasion of His 70th Birthday","day":"03","has_accepted_license":"1","page":"20 - 35","publication":"Rainbow of Computer Science","citation":{"mla":"Edelsbrunner, Herbert, and Michael Kerber. “Covering and Packing with Spheres by Diagonal Distortion in R^n.” Rainbow of Computer Science, edited by Cristian Calude et al., vol. 6570, Springer, 2011, pp. 20–35, doi:10.1007/978-3-642-19391-0_2.","short":"H. Edelsbrunner, M. Kerber, in:, C. Calude, G. Rozenberg, A. Salomaa (Eds.), Rainbow of Computer Science, Springer, 2011, pp. 20–35.","chicago":"Edelsbrunner, Herbert, and Michael Kerber. “Covering and Packing with Spheres by Diagonal Distortion in R^n.” In Rainbow of Computer Science, edited by Cristian Calude, Grzegorz Rozenberg, and Arto Salomaa, 6570:20–35. Dedicated to Hermann Maurer on the Occasion of His 70th Birthday. Springer, 2011. https://doi.org/10.1007/978-3-642-19391-0_2.","ama":"Edelsbrunner H, Kerber M. Covering and packing with spheres by diagonal distortion in R^n. In: Calude C, Rozenberg G, Salomaa A, eds. Rainbow of Computer Science. Vol 6570. Dedicated to Hermann Maurer on the Occasion of His 70th Birthday. Springer; 2011:20-35. doi:10.1007/978-3-642-19391-0_2","ista":"Edelsbrunner H, Kerber M. 2011.Covering and packing with spheres by diagonal distortion in R^n. In: Rainbow of Computer Science. LNCS, vol. 6570, 20–35.","ieee":"H. Edelsbrunner and M. Kerber, “Covering and packing with spheres by diagonal distortion in R^n,” in Rainbow of Computer Science, vol. 6570, C. Calude, G. Rozenberg, and A. Salomaa, Eds. Springer, 2011, pp. 20–35.","apa":"Edelsbrunner, H., & Kerber, M. (2011). Covering and packing with spheres by diagonal distortion in R^n. In C. Calude, G. Rozenberg, & A. Salomaa (Eds.), Rainbow of Computer Science (Vol. 6570, pp. 20–35). Springer. https://doi.org/10.1007/978-3-642-19391-0_2"},"date_published":"2011-05-03T00:00:00Z","alternative_title":["LNCS"],"type":"book_chapter","abstract":[{"lang":"eng","text":"We address the problem of covering ℝ n with congruent balls, while minimizing the number of balls that contain an average point. Considering the 1-parameter family of lattices defined by stretching or compressing the integer grid in diagonal direction, we give a closed formula for the covering density that depends on the distortion parameter. We observe that our family contains the thinnest lattice coverings in dimensions 2 to 5. We also consider the problem of packing congruent balls in ℝ n , for which we give a closed formula for the packing density as well. Again we observe that our family contains optimal configurations, this time densest packings in dimensions 2 and 3."}],"title":"Covering and packing with spheres by diagonal distortion in R^n","ddc":["000"],"status":"public","intvolume":" 6570","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","_id":"3796","file":[{"relation":"main_file","file_id":"4640","checksum":"aaf22b4d7bd4277ffe8db532119cf474","date_updated":"2020-07-14T12:46:16Z","date_created":"2018-12-12T10:07:42Z","access_level":"open_access","file_name":"IST-2016-539-v1+1_2011-B-01-CoveringPacking.pdf","content_type":"application/pdf","file_size":436875,"creator":"system"}],"oa_version":"Submitted Version","pubrep_id":"539"},{"author":[{"full_name":"Chen, Chao","id":"3E92416E-F248-11E8-B48F-1D18A9856A87","first_name":"Chao","last_name":"Chen"},{"full_name":"Kerber, Michael","first_name":"Michael","last_name":"Kerber","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-8030-9299"}],"date_created":"2018-12-11T12:02:22Z","date_updated":"2021-01-12T07:42:17Z","oa_version":"None","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","_id":"3270","year":"2011","status":"public","title":"Persistent homology computation with a twist","publication_status":"published","publisher":"TU Dortmund","department":[{"_id":"HeEd"}],"abstract":[{"text":"The persistence diagram of a filtered simplicial com- plex is usually computed by reducing the boundary matrix of the complex. We introduce a simple op- timization technique: by processing the simplices of the complex in decreasing dimension, we can “kill” columns (i.e., set them to zero) without reducing them. This technique completely avoids reduction on roughly half of the columns. We demonstrate that this idea significantly improves the running time of the reduction algorithm in practice. We also give an output-sensitive complexity analysis for the new al- gorithm which yields to sub-cubic asymptotic bounds under certain assumptions.","lang":"eng"}],"publist_id":"3376","type":"conference","conference":{"end_date":"2011-03-30","location":"Morschach, Switzerland","start_date":"2011-03-28","name":"EuroCG: European Workshop on Computational Geometry"},"date_published":"2011-01-01T00:00:00Z","language":[{"iso":"eng"}],"citation":{"chicago":"Chen, Chao, and Michael Kerber. “Persistent Homology Computation with a Twist,” 197–200. TU Dortmund, 2011.","mla":"Chen, Chao, and Michael Kerber. Persistent Homology Computation with a Twist. TU Dortmund, 2011, pp. 197–200.","short":"C. Chen, M. Kerber, in:, TU Dortmund, 2011, pp. 197–200.","ista":"Chen C, Kerber M. 2011. Persistent homology computation with a twist. EuroCG: European Workshop on Computational Geometry, 197–200.","apa":"Chen, C., & Kerber, M. (2011). Persistent homology computation with a twist (pp. 197–200). Presented at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland: TU Dortmund.","ieee":"C. Chen and M. Kerber, “Persistent homology computation with a twist,” presented at the EuroCG: European Workshop on Computational Geometry, Morschach, Switzerland, 2011, pp. 197–200.","ama":"Chen C, Kerber M. Persistent homology computation with a twist. In: TU Dortmund; 2011:197-200."},"quality_controlled":"1","page":"197 - 200","day":"01","month":"01"},{"alternative_title":["LNCS"],"type":"conference","abstract":[{"lang":"eng","text":"Using ideas from persistent homology, the robustness of a level set of a real-valued function is defined in terms of the magnitude of the perturbation necessary to kill the classes. Prior work has shown that the homology and robustness information can be read off the extended persistence diagram of the function. This paper extends these results to a non-uniform error model in which perturbations vary in their magnitude across the domain."}],"intvolume":" 6281","ddc":["000"],"status":"public","title":"Persistent homology under non-uniform error","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","_id":"3849","oa_version":"Submitted Version","file":[{"file_name":"IST-2016-537-v1+1_2010-P-05-NonuniformError.pdf","access_level":"open_access","file_size":142357,"content_type":"application/pdf","creator":"system","relation":"main_file","file_id":"4994","date_created":"2018-12-12T10:13:13Z","date_updated":"2020-07-14T12:46:17Z","checksum":"af61e1c2bb42f3d556179d4692caeb1b"}],"pubrep_id":"537","scopus_import":1,"has_accepted_license":"1","day":"10","page":"12 - 23","citation":{"ama":"Bendich P, Edelsbrunner H, Kerber M, Patel A. Persistent homology under non-uniform error. In: Vol 6281. Springer; 2010:12-23. doi:10.1007/978-3-642-15155-2_2","apa":"Bendich, P., Edelsbrunner, H., Kerber, M., & Patel, A. (2010). Persistent homology under non-uniform error (Vol. 6281, pp. 12–23). Presented at the MFCS: Mathematical Foundations of Computer Science, Brno, Czech Republic: Springer. https://doi.org/10.1007/978-3-642-15155-2_2","ieee":"P. Bendich, H. Edelsbrunner, M. Kerber, and A. Patel, “Persistent homology under non-uniform error,” presented at the MFCS: Mathematical Foundations of Computer Science, Brno, Czech Republic, 2010, vol. 6281, pp. 12–23.","ista":"Bendich P, Edelsbrunner H, Kerber M, Patel A. 2010. Persistent homology under non-uniform error. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 6281, 12–23.","short":"P. Bendich, H. Edelsbrunner, M. Kerber, A. Patel, in:, Springer, 2010, pp. 12–23.","mla":"Bendich, Paul, et al. Persistent Homology under Non-Uniform Error. Vol. 6281, Springer, 2010, pp. 12–23, doi:10.1007/978-3-642-15155-2_2.","chicago":"Bendich, Paul, Herbert Edelsbrunner, Michael Kerber, and Amit Patel. “Persistent Homology under Non-Uniform Error,” 6281:12–23. Springer, 2010. https://doi.org/10.1007/978-3-642-15155-2_2."},"date_published":"2010-08-10T00:00:00Z","publist_id":"2333","file_date_updated":"2020-07-14T12:46:17Z","publisher":"Springer","department":[{"_id":"HeEd"}],"publication_status":"published","year":"2010","volume":6281,"date_updated":"2021-01-12T07:52:38Z","date_created":"2018-12-11T12:05:30Z","author":[{"full_name":"Bendich, Paul","last_name":"Bendich","first_name":"Paul","id":"43F6EC54-F248-11E8-B48F-1D18A9856A87"},{"last_name":"Edelsbrunner","first_name":"Herbert","orcid":"0000-0002-9823-6833","id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","full_name":"Edelsbrunner, Herbert"},{"orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","last_name":"Kerber","first_name":"Michael","full_name":"Kerber, Michael"},{"full_name":"Patel, Amit","id":"34A254A0-F248-11E8-B48F-1D18A9856A87","last_name":"Patel","first_name":"Amit"}],"month":"08","quality_controlled":"1","oa":1,"language":[{"iso":"eng"}],"doi":"10.1007/978-3-642-15155-2_2","conference":{"name":"MFCS: Mathematical Foundations of Computer Science","end_date":"2010-08-27","start_date":"2010-08-23","location":"Brno, Czech Republic"}},{"abstract":[{"text":"Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance ε in Hausdorff distance, as the Minkowski sum of another polygonal shape with a disk of fixed radius? If it does, we also seek a preferably simple solution shape P;P’s offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give a decision algorithm for fixed radius in O(nlogn) time that handles any polygonal shape. For convex shapes, the complexity drops to O(n), which is also the time required to compute a solution shape P with at most one more vertex than a vertex-minimal one.","lang":"eng"}],"publist_id":"2334","type":"conference","date_created":"2018-12-11T12:05:30Z","date_updated":"2021-01-12T07:52:39Z","oa_version":"None","author":[{"last_name":"Berberich","first_name":"Eric","full_name":"Berberich, Eric"},{"full_name":"Halperin, Dan","first_name":"Dan","last_name":"Halperin"},{"orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","last_name":"Kerber","first_name":"Michael","full_name":"Kerber, Michael"},{"first_name":"Roza","last_name":"Pogalnikova","full_name":"Pogalnikova, Roza"}],"title":"Polygonal reconstruction from approximate offsets","status":"public","publication_status":"published","publisher":"TU Dortmund","department":[{"_id":"HeEd"}],"_id":"3850","year":"2010","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","day":"01","month":"01","language":[{"iso":"eng"}],"conference":{"end_date":"2010-03-24","location":"Dortmund, Germany","start_date":"2010-03-22","name":"EuroCG: European Workshop on Computational Geometry"},"date_published":"2010-01-01T00:00:00Z","quality_controlled":"1","page":"12 - 23","citation":{"short":"E. Berberich, D. Halperin, M. Kerber, R. Pogalnikova, in:, TU Dortmund, 2010, pp. 12–23.","mla":"Berberich, Eric, et al. Polygonal Reconstruction from Approximate Offsets. TU Dortmund, 2010, pp. 12–23.","chicago":"Berberich, Eric, Dan Halperin, Michael Kerber, and Roza Pogalnikova. “Polygonal Reconstruction from Approximate Offsets,” 12–23. TU Dortmund, 2010.","ama":"Berberich E, Halperin D, Kerber M, Pogalnikova R. Polygonal reconstruction from approximate offsets. In: TU Dortmund; 2010:12-23.","ieee":"E. Berberich, D. Halperin, M. Kerber, and R. Pogalnikova, “Polygonal reconstruction from approximate offsets,” presented at the EuroCG: European Workshop on Computational Geometry, Dortmund, Germany, 2010, pp. 12–23.","apa":"Berberich, E., Halperin, D., Kerber, M., & Pogalnikova, R. (2010). Polygonal reconstruction from approximate offsets (pp. 12–23). Presented at the EuroCG: European Workshop on Computational Geometry, Dortmund, Germany: TU Dortmund.","ista":"Berberich E, Halperin D, Kerber M, Pogalnikova R. 2010. Polygonal reconstruction from approximate offsets. EuroCG: European Workshop on Computational Geometry, 12–23."}},{"month":"10","quality_controlled":"1","oa":1,"language":[{"iso":"eng"}],"doi":"10.1109/TVCG.2010.139","publist_id":"2253","file_date_updated":"2020-07-14T12:46:21Z","publisher":"IEEE","department":[{"_id":"HeEd"}],"publication_status":"published","year":"2010","volume":16,"date_created":"2018-12-11T12:05:47Z","date_updated":"2021-01-12T07:53:04Z","author":[{"full_name":"Bendich, Paul","id":"43F6EC54-F248-11E8-B48F-1D18A9856A87","last_name":"Bendich","first_name":"Paul"},{"id":"3FB178DA-F248-11E8-B48F-1D18A9856A87","orcid":"0000-0002-9823-6833","first_name":"Herbert","last_name":"Edelsbrunner","full_name":"Edelsbrunner, Herbert"},{"last_name":"Kerber","first_name":"Michael","orcid":"0000-0002-8030-9299","id":"36E4574A-F248-11E8-B48F-1D18A9856A87","full_name":"Kerber, Michael"}],"scopus_import":1,"has_accepted_license":"1","day":"28","page":"1251 - 1260","citation":{"short":"P. Bendich, H. Edelsbrunner, M. Kerber, IEEE Transactions of Visualization and Computer Graphics 16 (2010) 1251–1260.","mla":"Bendich, Paul, et al. “Computing Robustness and Persistence for Images.” IEEE Transactions of Visualization and Computer Graphics, vol. 16, no. 6, IEEE, 2010, pp. 1251–60, doi:10.1109/TVCG.2010.139.","chicago":"Bendich, Paul, Herbert Edelsbrunner, and Michael Kerber. “Computing Robustness and Persistence for Images.” IEEE Transactions of Visualization and Computer Graphics. IEEE, 2010. https://doi.org/10.1109/TVCG.2010.139.","ama":"Bendich P, Edelsbrunner H, Kerber M. Computing robustness and persistence for images. IEEE Transactions of Visualization and Computer Graphics. 2010;16(6):1251-1260. doi:10.1109/TVCG.2010.139","apa":"Bendich, P., Edelsbrunner, H., & Kerber, M. (2010). Computing robustness and persistence for images. IEEE Transactions of Visualization and Computer Graphics. IEEE. https://doi.org/10.1109/TVCG.2010.139","ieee":"P. Bendich, H. Edelsbrunner, and M. Kerber, “Computing robustness and persistence for images,” IEEE Transactions of Visualization and Computer Graphics, vol. 16, no. 6. IEEE, pp. 1251–1260, 2010.","ista":"Bendich P, Edelsbrunner H, Kerber M. 2010. Computing robustness and persistence for images. IEEE Transactions of Visualization and Computer Graphics. 16(6), 1251–1260."},"publication":"IEEE Transactions of Visualization and Computer Graphics","date_published":"2010-10-28T00:00:00Z","type":"journal_article","issue":"6","abstract":[{"lang":"eng","text":"We are interested in 3-dimensional images given as arrays of voxels with intensity values. Extending these values to acontinuous function, we study the robustness of homology classes in its level and interlevel sets, that is, the amount of perturbationneeded to destroy these classes. The structure of the homology classes and their robustness, over all level and interlevel sets, can bevisualized by a triangular diagram of dots obtained by computing the extended persistence of the function. We give a fast hierarchicalalgorithm using the dual complexes of oct-tree approximations of the function. In addition, we show that for balanced oct-trees, thedual complexes are geometrically realized in $R^3$ and can thus be used to construct level and interlevel sets. We apply these tools tostudy 3-dimensional images of plant root systems."}],"intvolume":" 16","ddc":["000"],"title":"Computing robustness and persistence for images","status":"public","user_id":"4435EBFC-F248-11E8-B48F-1D18A9856A87","_id":"3901","file":[{"access_level":"open_access","file_name":"IST-2016-536-v1+1_2010-J-02-PersistenceforImages.pdf","file_size":721994,"content_type":"application/pdf","creator":"system","relation":"main_file","file_id":"5262","checksum":"f6d813c04f4b46023cec6b9a17f15472","date_created":"2018-12-12T10:17:10Z","date_updated":"2020-07-14T12:46:21Z"}],"oa_version":"Submitted Version","pubrep_id":"536"}]