Homepage
My research focuses on the design, analysis and implementation of efficient algorithms
in algebraic topology, computational geometry, real algebraic geometry,
and symbolic computation, with the goal to bridge the gap between mathematical theory and
application areas. My current emphasis lies on the theory of persistent homology
and its applications in the analysis of scientific data.
- Michael Kerber, Sharath Raghvendra: Approximation and Streaming Algorithms for Projective Clustering via Random Projections. arXiv:1407.2063
- Dan Halperin, Michael Kerber, Doron Shaharabani: The Offset Filtration of Convex Objects. arXiv:1407.6132
- Aruni Choudhary, Michael Kerber: Local Doubling Dimension of Point Sets. arXiv:1406.4822
- Chen Gu, Leonidas Guibas, Michael Kerber: Topology-driven Trajectory Synthesis with an Example on Retinal Cell Motions. 14th International Workshop on Algorithms in Bioinformatics (WABI 2014), pp.326-340. (pdf)
© Springer, 2014. The final publication is available via Springer
- Mabel Iglesias-Ham, Michael Kerber, Caroline Uhler: Sphere Packing with Limited Overlap. Accepted for the Canadian Conference on Computational Geometry (CCCG 2014). Available at arXiv:1401.0468
- Ulrich Bauer, Michael Kerber, Jan Reininghaus, Hubert Wagner: PHAT - Persistent Homology Algorithms Toolbox. 4th International Congress of Mathematical Software (ICMS 2014). (pdf)
© Springer, 2014. The original publication is available at www.springerlink.com
- Ulrich Bauer, Michael Kerber, Jan Reininghaus: Distributed Computation of Persistent Homology. Algorithm Engineering and Experiments (ALENEX) 2014. Available at arxiv:1310.0710
- Michael Kerber, R.Sharathkumar: Approximate Cech Complex in Low and High Dimensions. 24th International Symposium on Algorithms and Computation (ISAAC 2013), LNCS 8283, pp.666-676. Available at arXiv:1307.3272
- Haochen Tang, Michael Kerber, Qixing Huang, Leo Guibas: Locating Lucrative Passengers for Taxicab Drivers. 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2013), pp.504-507 (pdf)
- Yang Li, Qixing Huang, Michael Kerber, Lin Zhang, Leo Guibas: Large-Scale Joint Map Matching of GPS Traces. 21st ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL GIS 2013), pp.214-223 (pdf)
- Michael Kerber: Embedding the Dual Complex of Hyper-Rectangular Partitions. Journal of Computational Geometry 4 (1) pp. 13-37, 2013 (link).
- Ulrich Bauer, Michael Kerber, Jan Reininghaus: Clear and Compress: Computing Persistent Homology in Chunks. TopoInVis 2013 (Best Paper Award). Available at arxiv:1303.0477
- Chao Chen, Michael Kerber: An Output Sensitive Algorithm for Persistent Homology. Computational Geometry: Theory and Applications 46 (4) pp. 435-447, 2013 - Special Issue on the 27th Annual Symposium on Computational Geometry (link). The conference version appeared in the Proceedings of the 27th Annual Symposium on Computational Geometry, pp. 207-215 (SoCG 2011) (pdf, ps)
© ACM, 2011.
- Michael Kerber, Herbert Edelsbrunner: 3D Kinetic Alpha Complexes and Their Implementation. Algorithm Engineering and Experiments (ALENEX) 2013. The extended version The Medusa of Spatial Sorting: 3D Kinetic Alpha Complexes and Implementation is available at arXiv:1209.5434
- Herbert Edelsbrunner, Carl-Philipp Heisenberg, Michael Kerber, Gabriel Krens: The Medusa of Spatial Sorting: Topological Construction. arXiv:1207.6474
- Eric Berberich, Dan Halperin, Michael Kerber, Roza Pogalnikova: Deconstructing Approximate Offsets. Discrete and Computational Geometry 48 (2012), pp.964-989 (link). The conference version appeared in the Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG 2011), pp. 187-196 (pdf, ps), © ACM, 2011
An extended abstract was presented at the 26th European Workshop on Computational Geometry (EuroCG 2010) (pdf)
- Herbert Edelsbrunner, Michael Kerber: Alexander Duality for Functions: the Persistent Behavior of Land and Water and Shore. Proceedings of the 28th Annual Symposium on Computational Geometry, pp. 249-258 (SoCG 2012) (pdf)
© ACM, 2012.
This is the authors' version of the work.
It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in the
Proceedings of the 2012 Annual Symposium on Computational Geometry
(SoCG'12)
- Herbert Edelsbrunner, Michael Kerber: Dual Complexes of Cubical Subdivisions of R^n. Discrete and Computational Geometry 47 (2012), pp.393-414 (pdf) © Springer, 2012.
- Gavin Brown, Michael Kerber, Miles Reid: Fano 3-folds in codimension 4, Tom and Jerry, Part I. Compositio Mathematica 148 (4) pp.1171-1194, 2012 (link). Available at arXiv:1009.4313
- Michael Kerber, Michael Sagraloff: A Worst-case Bound for Topology Computation of Algebraic Curves. Journal of Symbolic Computation 47 (2012), pp.239-258. Available at arXiv:1104.1510
- Michael Kerber, Michael Sagraloff: Efficient Real Root Approximation. Proceedings of the 36th International Symposium on Symbolic and Algebraic Computation (ISSAC 2011), pp. 209-216 (pdf, ps) Supplementary material: pdf, ps
© ACM, 2011.
This is the authors' version of the work.
It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in
ISSAC'11: International Symposium on Symbolic and Algebraic Computation Proceedings
An improved version of the result is available as Root Refinement for Real Polynomials arXiv:1104.1362
- Eric Berberich, Michael Hemmer, Michael Kerber: A Generic Algebraic Kernel for Non-linear Geometric Applications. Proceedings of the 27th Annual Symposium on Computational Geometry, pp. 179-186 (SoCG 2011) (pdf, ps)
© ACM, 2011.
This is the authors' version of the work.
It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in the
Proceedings of the 2011 Annual Symposium on Computational Geometry
(SoCG'11)
- Chao Chen, Michael Kerber: Persistent Homology Computation With a Twist. 27th European Workshop on Computational Geometry (EuroCG 2011). (pdf)
- Herbert Edelsbrunner, Michael Kerber: Covering and packing with spheres by diagonal distortion in R^n. Rainbow of Computer Science - Essays Dedicated to Hermann Maurer on the Occasion of His 70th Birthday, eds. C. Calude, G. Rozenberg and A. Salomaa, LNCS 6570, pp. 20-35. (pdf)
- Michael Kerber, Michael Sagraloff: A Note on the Complexity of Real Algebraic Hypersurfaces. Journal on Graphs and Combinatorics 27 (3) pp. 419-430 (pdf)
© Springer, 2011. The original publication is available at www.springerlink.com
An extended abstract of this work was presented
at 7th Japan Conference on Computational Geometry and Graphs (JCCGG'09) (pdf, ps)
- Paul Bendich, Herbert Edelsbrunner, Michael Kerber: Computing Robustness and Persistence for Images. IEEE Transactions on Visualization and Computer Graphics 16 (2010), pp. 1251-1260 (pdf) © IEEE 2010
- Paul Bendich, Herbert Edelsbrunner, Michael Kerber, Amit Patel: Persistent Homology under Non-uniform Error. Invited paper for the 35th International Symposium on Mathematical Foundations of Computer Science (MFCS 2010), LNCS 6281, pp. 12-23 (pdf)
© Springer, 2010. The original publication is available at www.springerlink.com
- Eric Berberich, Efi Fogel, Dan Halperin, Michael Kerber, Ophir Setter: Arrangements on Parametric Surfaces II: Concretizations and Applications. Mathematics in Computer Science 4 (1), pp.67-91 (pdf) © Birkhäuser 2010
- Michael Kerber: Geometric Algorithms for Algebraic Curves and Surfaces. PhD Thesis, Saarland University, 2009 (pdf, ps)
- Michael Sagraloff, Michael Kerber, Michael Hemmer: Certified Complex Root Isolation via Adaptive Root Separation Bounds. 9th Asian Symposium on Computer Mathematics (ASCM'09) (pdf)
- Eric Berberich, Michael Kerber, Michael Sagraloff: An Efficient Algorithm for the Stratification and Triangulation of Algebraic Surfaces. Computational Geometry: Theory and Applications 43 (3) pp. 257-278 - Special Issue on 24th Annual Symposium on Computational Geometry
- Michael Kerber: On the Complexity of Reliable Root Approximation. 11th International Workshop on Computer Algebra in Scientific Computing (CASC'09). LNCS 5743, pp. 155-167 (pdf, ps)
© Springer, 2009. The original publication is available at www.springerlink.com
- Michael Kerber: Division-Free Computation of Subresultants Using Bezout Matrices. International Journal of Computer Mathematics 86 (12) pp. 2186-2200, 2009
- Eric Berberich, Michael Kerber, Michael Sagraloff: Exact Geometric-Topological Analysis of Algebraic Surfaces. Proceedings of the twenty-fourth Annual Symposium on Computational Geometry (SoCG 08), pp. 164-173
(pdf, ps)
© ACM, 2008.
This is the authors' version of the work.
It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in the
Proceedings of the twenty-fourth Annual Symposium on Computational Geometry
(SoCG'08) http://doi.acm.org/10.1145/1377676.1377703
An extended abstract of this work was presented at the 24th European Workshop on Computational Geometry (pdf, ps).
- Pavel Emeliyanenko, Michael Kerber: Visualizing and Exploring Planar Algebraic Arrangements - a Web Application. Video presented at the 24th Annual Symposium on Computational Geometry (SoCG'08)
- Eric Berberich, Michael Kerber: Exact arrangements on Tori and Dupin cyclides. Proceedings of the 2008 ACM Symposium on Solid and Physical Modeling (SPM 2008), pp. 59-66
(pdf, ps)
© ACM, 2008.
This is the authors' version of the work.
It is posted here by permission of ACM for your personal use.
Not for redistribution. The definitive version was published in the
Proceedings of the ACM Solid and Physical Modelling Symposium (SPM 2008)
http://doi.acm.org/10.1145/1364901.1364912
An extended abstract of this work was presented at the 24th European Workshop on Computational Geometry (pdf, ps).
- Arno Eigenwillig, Michael Kerber: Exact and Efficient 2D-Arrangements of Arbitrary Algebraic Curves. Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2008), pp. 122-131 (pdf, ps).
© SIAM 2008. The provided download is an author-prepared version of the article.
- Arno Eigenwillig, Michael Kerber, Nicola Wolpert: Fast and Exact Geometric Analysis of Real Algebraic Plane Curves. Proceedings of the International Symposium on Symbolic and Algebraic Computation (ISSAC 2007), pp. 151-158 (pdf, ps).
© ACM, 2007. This is the authors' version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in the Proceedings of the 2007 International Symposium on Symbolic and Algebraic Computation (ISSAC 2007). http://doi.acm.org/10.1145/1277548.1277570
- Michael Kerber: Analysis of Real Algebraic Plane Curves. Diploma Thesis, Saarbrücken 2006 (pdf, ps).
Current:
Past events:
Oktober 2012-present: Junior Research Group Leader at Max-Planck-Center for Visual Computing and Communication, Saarbrücken, Germany
Oktober 2012-September 2013: Visiting Assistant Professor at Stanford University
November 2009 - September 2012: Postdoc at the Institute of Science and Technology (IST) Austria, Klosterneuburg, Austria
January - July 2010: Visiting Postdoc at Duke University, Computer Science Department
March - June 2005: Research Associate at University of Warwick, Mathematics Institute
- PHAT is collection of efficient implementations of persistent homology
- DIPHA is another package for the efficient computation of persistent homology on distributed systems
- Check out the xalci webdemo for plotting arrangements of algebraic curves and watch the video about it
- Also check out the CGAL webpage, especially the algebraic kernel package