Institute for Theoretical Computer Science ETH Zürich, CAB G33.1 Universitätsstrasse 6 CH-8092 Zürich Switzerland E-mail: URL: http://www.inf.ethz.ch/~hoffmann Tel: +41-44-632 73 90 Fax: +41-44-632 10 63 Office: CAB G33.1
	"Plane Graphs with Parity Constraints" with Oswin Aichholzer, Thomas Hackl, Alexander Pilz, Günter Rote, Bettina Speckmann, and Birgit Vogtenhuber. Appeared in Proc. 11th Algorithms and Data Struct. Sympos. (WADS '09), Lecture Notes in Computer Science, Volume 5664, Banff(AB), Canada, 2009, 13-24. "Wireless Localization with Vertex Guards is NP-hard" (PDF) with Tobias Christ. To appear in Proc. 21st Canadian Conference on Computational Geometry (CCCG '09), Vancouver, Canada, 2009, ?. "Convex Partitions with 2-Edge Connected Dual Graphs" with Marwan Al Jubeh, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth. Appeared in Proc. 15th Ann. Internat. Conf. Computing and Combinatorics (COCOON '09), Lecture Notes in Computer Science, Volume 5609, Niagara Falls (NY), U.S.A., 2009, 192-204. "Improved Bounds for Wireless Localization" with Tobias Christ, Yoshio Okamoto, and Takeaki Uno. To appear in Algorithmica, Volume ?, 2009, ?. "Pointed Binary Encompassing Trees: Simple and Optimal" with Bettina Speckmann, and Csaba D. Tóth. Appeared in Computational Geometry: Theory and Applications, Volume 43(1), 2010, 35-41. "The Euclidean Degree-4 Minimum Spanning Tree Problem is NP-hard" with Andrea Francke. Appeared in Proc. 25th Annu. Sympos. Comput. Geom. (SOCG '09), Århus, Denmark, 2009, 179-188. "Natural Wireless Localization is NP-hard" (PDF) with Tobias Christ, and Yoshio Okamoto. Appeared in Abstracts 25th European Workshop on Computational Geometry (EuroCG '09), Bruxelles, Belgium, 2009. "Improved Bounds for Wireless Localization" with Tobias Christ, Yoshio Okamoto, and Takeaki Uno. Appeared in Proc. 11th Scand. Workshop Algorithm Theory (SWAT '08), Lecture Notes in Computer Science, Volume 5124, Göteborg, Sweden, 2008, 77-89. "Disjoint Segments have Convex Partitions with 2-Edge Connected Dual Graphs" (PDF) (Gzipped Postscript) (Postscript) with Nadia Benbernou, Erik D. Demaine, Martin L. Demaine, Mashhood Ishaque, Diane L. Souvaine, and Csaba D. Tóth. Appeared in Proc. 19th Canadian Conference on Computational Geometry (CCCG '07), Ottawa, Canada, 2007, 13-16. (Erratum.) "Maximizing Maximal Angles for Plane Straight Line Graphs" with Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Attila Pór, Francisco Santos, Bettina Speckmann, and Birgit Vogtenhuber. Appeared in Proc. 10th Workshop Algorithms Data Struct. (WADS '07), Lecture Notes in Computer Science, Volume 4619, Halifax, Canada, 2007, 458-469. "An Adaptable and Extensible Geometry Kernel" with Susan Hert, Lutz Kettner, Sylvain Pion, and Michael Seel. Appeared in Computational Geometry: Theory and Applications, Volume 38(1-2), 2007, 16-36. "Maximizing Maximal Angles for Plane Straight Line Graphs" (PDF) with Oswin Aichholzer, Thomas Hackl, Clemens Huemer, Francisco Santos, Bettina Speckmann, and Birgit Vogtenhuber. Appeared in Abstracts 23rd European Workshop on Computational Geometry (EuroCG '07), Graz, Austria, 2007, 98-101. "The Minimum Weight Triangulation Problem with few Inner Points" with Yoshio Okamoto. Appeared in Computational Geometry: Theory and Applications, Volume 34(3), 2006, 149-158. "Coloring Octrees" with Udo Adamy, József Solymosi, and Miloš Stojaković. Appeared in Theoretical Computer Science, Volume 363(1), 2006, 11-17. "Spanning Trees across Axis-Parallel Segments" (PDF) (Gzipped Postscript) (Postscript) with Csaba D. Tóth. Appeared in Proc. 18th Canadian Conference on Computational Geometry (CCCG '06), Kingston(ON), Canada, 2006, 101-104. "Chordless Paths Through Three Vertices" with Robert Haas. Appeared in Theoretical Computer Science, Volume 351(3), 2006, 360-371. "The Traveling Salesman Problem with Few Interior Points" with Vladimir Deĭneko, Yoshio Okamoto, and Gerhard Woeginger. Appeared in Oper. Res. Lett., Volume 34(1), 2006, 106-110. "A Simple Linear Algorithm for Computing Rectilinear 3-Centers" Appeared in Computational Geometry: Theory and Applications, Volume 31(3), 2005, 150-165. "Pointed and Colored Binary Encompassing Trees" (PDF) (Gzipped Postscript) (Postscript) with Csaba D. Tóth. Appeared in Proc. 21st Annu. Sympos. Comput. Geom. (SOCG '05), Pisa, Italy, 2005, 81-90. "Pointed Binary Encompassing Trees: Simple and Optimal" (PDF) (Gzipped Postscript) (Postscript) with Csaba D. Tóth. Appeared in Abstracts 21st European Workshop on Computational Geometry (EuroCG '05), Eindhoven, Netherlands, 2005, 93-96. "Pointed Binary Encompassing Trees: Simple and Optimal" with Csaba D. Tóth. Appeared in Abstracts 14th Annual Fall Workshop Comput. Geom., Cambridge (MA), USA, 2004, 28-29. Invited to a special issue of Computational Geometry: Theory and Applications. "Chordless Paths Through Three Vertices" with Robert Haas. Appeared in Proc. Internat. Workshop on Parameterized and Exact Computation (IWPEC '04), Lecture Notes in Computer Science, Volume 3162, Bergen, Norway, 2004, 25-36. "The Minimum Weight Triangulation Problem with Few Interior Points" with Yoshio Okamoto. Appeared in Proc. Internat. Workshop on Parameterized and Exact Computation (IWPEC '04), Lecture Notes in Computer Science, Volume 3162, Bergen, Norway, 2004, 200-212. "The Traveling Salesman Problem with Few Interior Points" with Vladimir Deĭneko, Yoshio Okamoto, and Gerhard Woeginger. Appeared in Proc. 10th Ann. Internat. Conf. Computing and Combinatorics (COCOON '04), Lecture Notes in Computer Science, Volume 3106, Jeju Island, Korea, 2004, 268-277. "Coloring Octrees" with Udo Adamy, József Solymosi, and Miloš Stojaković. Appeared in Proc. 10th Ann. Internat. Conf. Computing and Combinatorics (COCOON '04), Lecture Notes in Computer Science, Volume 3106, Jeju Island, Korea, 2004, 62-71. "Pointed Binary Encompassing Trees" with Bettina Speckmann, and Csaba D. Tóth. Appeared in Proc. 9th Scand. Workshop Algorithm Theory (SWAT '04), Lecture Notes in Computer Science, Volume 3111, Humlebæk, Denmark, 2004, 442-454. "PushPush-k is PSPACE-Complete" (Gzipped Postscript) (Postscript) with Erik D. Demaine, and Markus Holzer. Appeared in Proc. 3rd Internat. Conf. Fun with Algorithms (FUN '04), Isola d'Elba, Tuscany, Italy, 2004, 159-170. Preprint. "New Nomogram for Foetal Weight Estimation based on Hadlock's Two-parameter Formula" with Giordana M. Beutler, Juozas Kurmanavicius, Emo Welzl, Renate Huch, and Michael Bajka. Appeared in Ultraschall in der Medizin, Volume 25(1), 2004, 58-64. "Pointed Binary Encompassing Trees" (PDF) (Gzipped Postscript) (Postscript) with Bettina Speckmann, and Csaba D. Tóth. Appeared in Abstracts 20th European Workshop on Computational Geometry (EuroCG '04), Seville, Spain, 2004, 131-134. "Alternating Paths through Disjoint Line Segments" with Csaba D. Tóth. Appeared in Information Processing Letters, Volume 87(6), 2003, 287-294. "Degree Bounds for Constrained Pseudo-Triangulations" (PDF) (Gzipped Postscript) (Postscript) with Oswin Aichholzer, Bettina Speckmann, and Csaba D. Tóth. Appeared in Proc. 15th Canadian Conference on Computational Geometry (CCCG '03), Halifax(NS), Canada, 2003, 155-158. "Pushing Blocks is Hard" with Erik D. Demaine, Martin L. Demaine, and Joseph O'Rourke. Appeared in Computational Geometry: Theory and Applications, Volume 26(1), 2003, 21-36. "Segment Endpoint Visibility Graphs are Hamiltonian" with Csaba D. Tóth. Appeared in Computational Geometry: Theory and Applications, Volume 26(1), 2003, 47-68. "Push-2F is PSPACE-Complete" (PDF) (Gzipped Postscript) (Postscript) with Erik D. Demaine, and Robert A. Hearn. Appeared in Proc. 14th Canadian Conference on Computational Geometry (CCCG '02), Lethbridge(AB), Canada, 2002, 31-35. "Connecting Points in the Presence of Obstacles in the Plane" (PDF) (Gzipped Postscript) (Postscript) with Csaba D. Tóth. Appeared in Proc. 14th Canadian Conference on Computational Geometry (CCCG '02), Lethbridge(AB), Canada, 2002, 63-67. "Alternating Paths through Disjoint Line Segments" (PDF) (Gzipped Postscript) (Postscript) with Csaba D. Tóth. Appeared in Abstracts 18th European Workshop on Computational Geometry (EuroCG '02), Warsaw, 2002, 23-26. This is a revised and extended version. "An Adaptable and Extensible Geometry Kernel" (PDF) (Gzipped Postscript) (Postscript) with Susan Hert, Lutz Kettner, Sylvain Pion, and Michael Seel. Technical Report, Number 362, Institute for Theoretical Computer Science, ETH Zürich, September, 2001. Also appeared as MPI-I-2001-1-004 and INRIA RR-4270. "An Adaptable and Extensible Geometry Kernel" with Susan Hert, Lutz Kettner, Sylvain Pion, and Michael Seel. Appeared in Proc. 5th Workshop on Algorithm Engineering (WAE '01), Lecture Notes in Computer Science, Volume 2141, Århus, Denmark, August, 2001, 76-91. "Segment Endpoint Visibility Graphs are Hamiltonian" (PDF) (Gzipped Postscript) (Postscript) with Csaba D. Tóth. Appeared in Proc. 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo(ON), Canada, 2001, 109-112. Invited to a special issue of Computational Geometry: Theory and Applications. "Pushing Blocks is NP-complete for Noncrossing Solution Paths" (PDF) (Gzipped Postscript) (Postscript) with Erik D. Demaine. Appeared in Proc. 13th Canadian Conference on Computational Geometry (CCCG '01), Waterloo(ON), Canada, 2001, 65-68. Invited to a special issue of Computational Geometry: Theory and Applications. "Covering Polygons with Few Rectangles" (PDF) (Gzipped Postscript) (Postscript) Appeared in Abstracts 17th European Workshop on Computational Geometry (EuroCG '01), Berlin, 2001, 39-42. "Push-* is NP-hard" (PDF) (Gzipped Postscript) (Postscript) Appeared in Proc. 12th Canadian Conference on Computational Geometry (CCCG '00), Fredericton(NB), Canada, 2000, 205-210. "A Simple Linear Algorithm for Computing Rectangular Three-Centers" (PDF) (Gzipped Postscript) (Postscript) Appeared in Proc. 11th Canadian Conference on Computational Geometry (CCCG '99), Vancouver(BC), Canada, 1999, 72-75. Invited to a special issue of Computational Geometry: Theory and Applications.
	cc2ps, produces beautified C++ source code (postscript output), useful for slides and presentations. It does aggressive syntax coloring in the style of emacs. Also includes a Modula/Oberon version called mod2ps.
	Last Modified: $Date: 2009/08/27 13:15:13 $.