Wolfgang Mulzer
Institut für Informatik
Freie Universität Berlin
Takustraße 9
14195 Berlin
Germany

Office: Room 114
Office Hours: Tuesdays, 16:00–17:00
Phone: +49 30 838–75165 (–75103)
Fax: +49 30 838–75192
WWW (official): http://www.inf.fu-berlin.de/inst/ag-ti/members/mulzer.de.html

My CV ([pdf] and [ps.gz]).

Publications

Journals

• John Iacono and Wolfgang Mulzer.
  A Static Optimality Transformation with Applications to Planar Point Location.
  International Journal of Computational Geometry and Applications (IJCGA), to appear.
  Special issue on SoCG 2011.
  [pdf] [ps.gz] [arXiv]
• 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] [ps.gz] [link]
• Kevin Buchin, Maarten Löffler, Pat Morin, and Wolfgang Mulzer.
  Preprocessing Imprecise Points for Delaunay Triangulations: Simplified and Extended.
  Algorithmica, 61(3), 2011, pp. 674–693.
  [pdf] [ps.gz] [doi]
  
• 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] [ps.gz] [link]
• 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] [ps.gz] [doi]
  
• 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] [ps.gz] [doi]
  
• Nir Ailon, Bernard Chazelle, Kenneth L. Clarkson, Ding Liu, Wolfgang Mulzer, and C. Seshadhri.
  Self-Improving Algorithms.
  SIAM Journal on Computing (SICOMP), 40(2), 2011, pp. 350–375.
  [pdf] [ps.gz] [arXiv] [doi]
• 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] [ps.gz] [doi]
  
• Wolfgang Mulzer.
  A Note on Predecessor Searching in the Pointer Machine Model.
  Information Processing Letters (IPL) 109(13), 2009, pp. 726–729.
  [pdf] [ps.gz] [doi]
  
• Wolfgang Mulzer and Günter Rote.
  Minimum Weight Triangulation is NP-hard.
  Journal of the Association for Computing Machinery (JACM) 55(2), May 2008, Article 11.
  Technical report: [pdf] [ps.gz]
  Journal version: [pdf] [ps.gz] [doi] [gadgets and software]
  [comment]

Refereed Conferences

• Wolfgang Mulzer and Daniel Werner.
  Approximating Tverberg Points in Linear Time for Any Fixed Dimension.
  Proceedings of the 28th Annual ACM Symposium on Computational Geometry (SoCG), Chapel Hill, USA, 2012, to appear.
  [pdf] [ps.gz] [arXiv]
• Kenneth L. Clarkson, Wolfgang Mulzer, and C. Seshadhri.
  Self-Improving Algorithms for Coordinate-Wise Maxima.
  Proceedings of the 28th Annual ACM Symposium on Computational Geometry (SoCG), Chapel Hill, USA, 2012, to appear.
  [pdf] [ps.gz] [arXiv]
  
• Esther Ezra and Wolfgang Mulzer.
  Convex Hull of Imprecise Points in o(n log n) Time after Preprocessing.
  Proceedings of the 27th Annual ACM Symposium on Computational Geometry (SoCG), Paris, France, 2011, pp. 11–20.
  [pdf] [ps.gz] [arXiv]
  
• 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] [ps.gz]
  
• 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] [ps.gz]
  Proceedings version: [pdf] [ps.gz] [doi]
  
• Kevin Buchin, Maarten Löffler, Pat Morin, and Wolfgang Mulzer.
  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] [ps.gz] [doi]
  
• Bernard Chazelle and Wolfgang Mulzer.
  Computing Hereditary Convex Structures.
  Proceedings of the 25th Annual ACM Symposium on Computational Geometry (SoCG), Aarhus, Denmark, 2009, pp. 61–70.
  [pdf] [ps.gz] [doi]
  
• Bernard Chazelle and Wolfgang Mulzer.
  Markov Incremental Constructions.
  Proceedings of the 24th Annual ACM Symposium on Computational Geometry (SoCG), College Park, USA, 2008, pp. 156–163.
  [pdf] [ps.gz] [doi]
  
• Wolfgang Mulzer and Günter Rote.
  Minimum Weight Triangulation is NP-hard.
  Proceedings of the 22nd Annual ACM Symposium on Computational Geometry (SoCG), Sedona, USA, 2006, pp. 1–10.
  Technical report: [pdf] [ps.gz]
  Proceedings version: [pdf] [ps.gz] [doi] [gadgets and software]
  

Non-Refereed Conferences and Workshops

• Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Günter Rote, and André Schulz.
  Memory-Constrained Algorithms for Simple Polygons.
  Proceedings of the 28th European Workshop on Computational Geometry (EWCG), Assisi, Italy, 2012,
  [pdf] [ps.gz] [arXiv]
• Wolfgang Mulzer and Daniel Werner.
  A Lower Bound for Shallow Partitions.
  Proceedings of the 28th European Workshop on Computational Geometry (EWCG), Assisi, Italy, 2012,
  [pdf] [ps.gz] [arXiv]
• 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,
  [pdf] [ps.gz] [Full pdf] [Full ps.gz] [arXiv]
• 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] [ps.gz]
• 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] [ps.gz]
• 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] [ps.gz]

Technical Reports etc

• Wolfgang Mulzer.
  Low-Entropy Computational Geometry.
  Doctoral Thesis. Princeton University, 2010.
  [pdf] [ps.gz]
• 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 version: [pdf] [ps.gz] [doi]
• Wolfgang Mulzer.
  Minimum Dilation Triangulations for the Regular n-Gon.
  Masters Thesis. Freie Universität Berlin, 2004.
  [pdf] [ps.gz]
• Christian Knauer and Wolfgang Mulzer.
  Minimum Dilation Triangulations.
  Technical Report B-05-06. Freie Universität Berlin, April 2005.
  [ps.gz]
• Kenneth L. Clarkson, Wolfgang Mulzer, and C. Seshadhri.
  Self-Improving Algorithms for Convex Hulls.
  Appeared at SODA 2010
  [Note]