About

Wolfgang Mulzer

Wolfgang Mulzer

Freie Universität Berlin
Fachbereich Mathematik und Informatik
Institut für Informatik
AG Theoretische Informatik
Takustraße 9
D-14195 Berlin
Germany
Office: Room 114
Phone: +49 30 838–75165 (–75103)
Fax: +49 30 838–75192
E-mail: mulzer[at]inf.fu-berlin.de

CV

Detailed CV

Publications

Journals:

  1. Oswin Aichholzer,
    Vincent Kusters,
    Wolfgang Mulzer,
    Alexander Pilz, and
    Manuel Wettstein

    An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings

    International Journal of Computational Geometry and Applications (IJCGA), to appear
    Special issue on ISAAC 2015

    [pdf] [arXiv]

  2. Karl Bringmann and
    Wolfgang Mulzer

    Approximability of the Discrete Fréchet Distance

    Journal of Computational Geometry (JoCG), 7(2), 2016, pp. 46–76
    Special issue on SoCG 2015

    [pdf] [link]

  3. Wolfgang Mulzer and
    Yannik Stein

    Algorithms for Tolerant Tverberg Partitions

    International Journal of Computational Geometry and Applications (IJCGA), 24(4), 2014, pp. 261–273
    Special issue on ISAAC 2013

    [pdf] [arXiv] [doi]

  4. Maarten Löffler and
    Wolfgang Mulzer

    Unions of Onions: Preprocessing Imprecise Points for Fast Onion Decomposition

    Journal of Computational Geometry (JoCG), 5(1), 2014, pp. 1–13

    [pdf] [arXiv] [link]

  5. Wolfgang Mulzer and
    Daniel Werner

    Approximating Tverberg Points in Linear Time for Any Fixed Dimension

    Discrete and Computational Geometry (DCG), 50(2), September 2013, pp. 520–535

    [pdf] [arXiv] [doi]

  6. Esther Ezra and
    Wolfgang Mulzer

    Convex Hull of Points Lying on Lines in o(n log n) Time after Preprocessing

    Computational Geometry: Theory and Applications (CGTA), 46(4), 2013, pp. 417–434
    Special issue on SoCG 2011

    [pdf] [arXiv] [doi]

  7. John Iacono and
    Wolfgang Mulzer

    A Static Optimality Transformation with Applications to Planar Point Location

    International Journal of Computational Geometry and Applications (IJCGA), 22(4), 2012, pp. 327–340
    Special issue on SoCG 2011

    [pdf] [arXiv] [doi]

  8. Maarten Löffler and
    Wolfgang Mulzer

    Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent

    SIAM Journal on Computing (SICOMP), 41(4), 2012, pp. 941–974

    [pdf] [arXiv] [doi]

  9. Tetsuo Asano,
    Wolfgang Mulzer, and
    Yajun Wang

    Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons

    Journal of Graph Algorithms and Applications (JGAA), 15(5), 2011, pp. 569–586
    Special issue on WALCOM 2010

    [pdf] [doi]

  10. Tetsuo Asano,
    Wolfgang Mulzer,
    Günter Rote, and
    Yajun Wang

    Constant-Work-Space Algorithms for Geometric Problems

    Journal of Computational Geometry (JoCG), 2(1), 2011, pp. 46–68

    [pdf] [link]

  11. Bernard Chazelle and
    Wolfgang Mulzer

    Computing Hereditary Convex Structures

    Discrete and Computational Geometry (DCG), 45(4), June 2011, pp. 796–823
    Special Issue on SoCG 2009

    [pdf] [doi]

  12. Kevin Buchin and
    Wolfgang Mulzer

    Delaunay Triangulations in O(sort(n)) Time and More

    Journal of the Association for Computing Machinery (JACM), 58(2), April 2011, Article 6

    [pdf] [doi]

  13. Bernard Chazelle and
    Wolfgang Mulzer

    Markov Incremental Constructions

    Discrete and Computational Geometry (DCG), 42(3), October 2009, pp. 399–420
    Special Issue on SoCG 2008

    [pdf] [doi]

  14. Wolfgang Mulzer

    A Note on Predecessor Searching in the Pointer Machine Model

    Information Processing Letters (IPL), 109(13), 2009, pp. 726–729

    [pdf] [doi]



Refereed Conferences:

  1. Oswin Aichholzer,
    Vincent Kusters,
    Wolfgang Mulzer,
    Alexander Pilz, and
    Manuel Wettstein

    An Optimal Algorithm for Reconstructing Point Set Order Types from Radial Orderings

    Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), Nagoya, Japan, 2015, pp. 505–516.

    [pdf] [arXiv] [doi]

  2. Karl Bringmann and
    Wolfgang Mulzer

    Approximability of the Discrete Fréchet Distance

    Proceedings of the 31st International Symposium on Computational Geometry (SoCG), Eindhoven, The Netherlands, 2015, pp. 739–753

    [pdf] [doi]

  3. Wolfgang Mulzer and
    Yannik Stein

    Computational Aspects of the Colorful Carathéodory Theorem

    Proceedings of the 31st International Symposium on Computational Geometry (SoCG), Eindhoven, The Netherlands, 2015, pp. 44–58

    [pdf] [arXiv] [doi]

  4. Yves Brise,
    Kevin Buchin,
    Dustin Eversmann,
    Michael Hoffmann, and
    Wolfgang Mulzer

    Interference Minimization in Asymmetric Sensor Networks

    Proceedings of the 10th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), Wrozwław, Poland, 2014, pp. 135–151

    [pdf] [arXiv] [doi]

  5. Wolfgang Mulzer and
    Yannik Stein

    Algorithms for Tolerated Tverberg Partition

    Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC), Hong Kong, 2013, pp. 295–305

    [pdf] [arXiv] [doi]

  6. Oswin Aichholzer,
    Wolfgang Mulzer, and
    Alexander Pilz

    Flip Distance Between Triangulations of a Simple Polygon is NP-Complete

    Proceedings of the 21st Annual European Symposium on Algorithms (ESA), Sophia Antipolis, France, 2013, pp. 13–24

    [pdf] [arXiv] [doi]

  7. Maarten Löffler and
    Wolfgang Mulzer

    Unions of Onions

    Proceedings of the 13th Algorithms and Data Structures Symposium (WADS), London, Canada, 2013, pp. 487–498

    [pdf] [arXiv] [doi]

  8. Bernard Chazelle and
    Wolfgang Mulzer

    Data Structures on Event Graphs

    Proceedings of the 20th Annual European Symposium on Algorithms (ESA), Ljubljana, Slovenia, 2012, pp. 313–324

    [pdf] [arXiv] [doi]

  9. Wolfgang Mulzer and
    Daniel Werner

    Approximating Tverberg Points in Linear Time for Any Fixed Dimension

    Proceedings of the 28th Annual Symposium on Computational Geometry (SoCG), Chapel Hill, USA, 2012, pp. 303–310

    [pdf] [arXiv] [doi]

  10. Esther Ezra and
    Wolfgang Mulzer

    Convex Hull of Imprecise Points in o(n log n) Time after Preprocessing

    Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG), Paris, France, 2011, pp. 11–20

    [full version] [arXiv] [doi]

  11. Maarten Löffler and
    Wolfgang Mulzer

    Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent

    Proceedings of the 22nd ACM-SIAM Symposium on Discrete Algorithms (SODA), San Francisco, USA, 2011, pp. 1759–1777

    [pdf] [arXiv] [doi]

  12. Kevin Buchin and
    Wolfgang Mulzer

    Delaunay Triangulations in O(sort(n)) Time and More

    Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), Atlanta, USA, 2009, pp. 139–148

    [brief description] [pdf] [doi]

  13. Delaunay Triangulation of Imprecise Points Simplified and Extended

    Proceedings of the 11th Algorithms and Data Structures Symposium (WADS), Banff, Canada, 2009, pp. 131–143

    [pdf] [doi]

  14. Bernard Chazelle and
    Wolfgang Mulzer

    Computing Hereditary Convex Structures

    Proceedings of the 25th Annual Symposium on Computational Geometry (SoCG), Aarhus, Denmark, 2009, pp. 61–70

    [pdf] [doi]

  15. Bernard Chazelle and
    Wolfgang Mulzer

    Markov Incremental Constructions

    Proceedings of the 24th Annual Symposium on Computational Geometry (SoCG), College Park, USA, 2008, pp. 156–163

    [pdf] [doi]



Weakly-Refereed Conferences and Workshops:

  1. Yeganeh Bahoo,
    Bahareh Banyassady,
    Prosenjit Bose,
    Stephane Durocher, and
    Wolfgang Mulzer

    Finding the k-Visibility Region of a Point in a Simple Polygon in the Memory-Constrained Model

    Proceedings of the 32nd European Workshop on Computational Geometry (EWCG), Lugano, Switzerland, 2016

    [pdf] [arXiv]

  2. Wolfgang Mulzer and
    Yannik Stein

    Approximating the Colorful Carathéodory Theorem

    Proceedings of the 31st European Workshop on Computational Geometry (EWCG), Ljubljana, Slovenia, 2015, pp. 20–23

    [pdf] [arXiv]

  3. Heuna Kim,
    Wolfgang Mulzer, and
    Eunjin Oh

    The Number of Combinatorially Different Convex Hulls of Points in Lines

    Proceedings of the 31st European Workshop on Computational Geometry (EWCG), Ljubljana, Slovenia, 2015, pp. 161–164

    [pdf]

  4. Efficient Spanner Construction for Directed Transmission Graphs

    Proceedings of the 31st European Workshop on Computational Geometry (EWCG), Ljubljana, Slovenia, 2015, pp. 172–175

    [pdf] [arXiv]

  5. Low-Crossing Spanning Trees: an Alternative Proof and Experiments

    Proceedings of the 30th European Workshop on Computational Geometry (EWCG), Ein-Gedi, Israel, 2014

    [pdf]

  6. Wolfgang Mulzer and
    Yannik Stein

    Complexity of Finding Nearest Colorful Polytopes

    Proceedings of the 30th European Workshop on Computational Geometry (EWCG), Ein-Gedi, Israel, 2014

    [pdf] [arXiv]

  7. Maarten Löffler and
    Wolfgang Mulzer

    Unions of Onions

    Proceedings of the 29th European Workshop on Computational Geometry (EWCG), Brunswick, Germany, 2013, pp. 61–64

    [pdf] [arXiv]

  8. Oswin Aichholzer,
    Wolfgang Mulzer, and
    Alexander Pilz

    Flip Distance Between Triangulations of a Simple Polygon is NP-Complete

    Proceedings of the 29th European Workshop on Computational Geometry (EWCG), Brunswick, Germany, 2013, pp. 115–118

    [pdf] [arXiv]

  9. Wolfgang Mulzer and
    Paul Seiferth

    Computational Aspects of Triangulations with Bounded Dilation

    Proceedings of the 29th European Workshop on Computational Geometry (EWCG), Brunswick, Germany, 2013, pp. 123–126

    [pdf]

  10. Wolfgang Mulzer and
    Daniel Werner

    A Lower Bound for Shallow Partitions

    Proceedings of the 28th European Workshop on Computational Geometry (EWCG), Assisi, Italy, 2012, pp. 129–132

    [pdf] [arXiv]

  11. Wolfgang Mulzer and
    Daniel Werner

    Approximating Tverberg Points in Linear Time for Any Fixed Dimension

    Proceedings of the 28th European Workshop on Computational Geometry (EWCG), Assisi, Italy, 2012, pp. 165–168

    [pdf] [arXiv]

  12. Esther Ezra and
    Wolfgang Mulzer

    Convex Hull of Imprecise Points in o(n log n) Time after Preprocessing

    Proceedings of the 27th European Workshop on Computational Geometry (EWCG), Morschach, Switzerland, 2011, pp. 209–212

    [pdf] [arXiv]

  13. Kevin Buchin and
    Wolfgang Mulzer

    Linear-Time Delaunay Triangulations Simplified

    Proceedings of the 25th European Workshop on Computational Geometry (EWCG), Brussels, Belgium, 2009, pp. 235–238

    [pdf]

  14. Christian Knauer and
    Wolfgang Mulzer

    An Exclusion Region for the Minimum Dilation Triangulation

    Proceedings of the 21st European Workshop on Computational Geometry (EWCG), Eindhoven, The Netherlands, 2005, pp. 33–36

    [pdf]



Technical Reports etc:

  1. Sebastian Kürten and
    Wolfgang Mulzer

    LiveCG: an Interactive Visualization Environment for Computational Geometry

    Multimedia Proceedings of the 30 Annual ACM Symposium on Computational Geometry (SoCG), Kyoto, Japan, 2014, pp. 86–87

    [pdf] [video] [link] [doi]

  2. Wolfgang Mulzer

    Low-Entropy Computational Geometry

    Doctoral Thesis. Princeton University, 2010

    [pdf]

  3. Tetsuo Asano,
    Wolfgang Mulzer, and
    Yajun Wang

    A Constant-Work-Space Algorithm for Shortest Paths in Simple Polygons

    Accompanying an invited talk in Proceedings of the 4th Workshop on Algorithms and Computation (WALCOM), Dhaka, Bangladesh, 2010, pp. 9–20

    [Journal PDF] [doi]

  4. Christian Knauer and
    Wolfgang Mulzer

    Minimum Dilation Triangulations

    Technical Report B-05-06. Freie Universität Berlin, April 2005

    [ps.gz]

  5. Wolfgang Mulzer

    Minimum Dilation Triangulations for the Regular n-Gon

    Masters Thesis. Freie Universität Berlin, 2004

    [pdf]

Teaching Notes

AlP 3:


Algorithmische Geometrie:


Höhere Algorithmik:


Miscellaneous: