A | B | C | D | E | F 
 G | H | I | J | K | L | M 
 N | O | P | Q | R | S | T 
 U | V | W | X | Y | Z 
max planck institut
informatik
mpii logo Minerva of the Max Planck Society

Homepage


NOTE: I am no longer at this institute. I first moved to the Universität Greifswald and finally ended up at the Universität Stuttgart.


Bodden near Wampen

Stefan Funke

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Building 46.1, Room 308
Stuhlsatzenhausweg 85
66123 Saarbrücken
Germany

Email: Get my email address via email
Phone: +49 681 9325 108
Fax: +49 681 9325 199


Research Interests



Misc



Courses

Short CV



Publications


  1. On the Locality of Extracting a 2-Manifold in R3
    Dumitriu, Funke, Kutz, Milosavljevic
    accepted at 11th Scandinavian Workshop on Algorithm Theory (SWAT) 2008, Gothenburg
    preliminary version was presented at 24th European Workshop on Computational Geometry (EWCG) 2008, Nancy
  2. Power Assignment Problems in Wireless Communication: Covering Points by Disks, Reaching few Receivers Quickly, and Energy-efficient Travelling Salesman Tours
    Funke, Laue, Lotker, Naujoks
    accepted at 4th IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS) 2008, Santorini
  3. How much Geometry it takes to Reconstruct a 2-Manifold in R3
    Dumitriu, Funke, Kutz, Milosavljevic
    accepted at 10th Workshop on Algorithm Engineering and Experimentation (ALENEX) 2008, San Francisco
  4. Optimal Triangulation of a Polygon with Steiner Points
    Aronov, Asano, Funke
    accepted at 18th Int. Symp. on Algorithms and Computation (ISAAC) 2007, Sendai
  5. Fast Routing in Road Networks With Transit Nodes
    Bast, Funke, Sanders, Schultes
    Science, Apr 27th, 2007
  6. Minimum-Energy Broadcast with few Senders
    Funke, Laue, Naujoks
    accepted for 3rd IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS) 2007, Santa Fe
  7. Information Brokerage via location-free Double Rulings
    Funke, Rauf
    accepted at 6th Int. Conf. on ADHOC Networks and Wireless (ADHOC-NOW) 2007, Morelia
  8. Guaranteed-delivery Geographic Routing under uncertain Location Information
    Funke, Milosavljevic
    accepted for 26th Ann. IEEE Conference on Computer Communication (INFOCOM) 2007, Anchorage
  9. Bounded-hop energy-efficient Broadcast in low-dimensional Metrics
    Funke, Laue
    Proc. 24th Int. Symposium on Theoretical Aspects of Computer Science (STACS) 2007, Aachen
  10. In Transit to Constant Time Shortest-Path Queries in Road Networks
    Bast, Funke, Matijevic, Sanders, Schultes
    Proc. 9th Workshop on Algorithm Engineering and Experimentation (ALENEX) 2007, New Orleans
  11. Network Sketching or: "How much Geometry hides in Connectivity? - Part II"
    Funke, Milosavljevic
    Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2007, New Orleans
  12. Hole Detection or: "How much Geometry hides in Connectivity?"
    Funke, Klein
    Proc. 22nd ACM Symposium on Computational Geometry (SoCG) 2006, Sedona
  13. Distance-sensitive Information Brokerage in Sensor Networks
    Funke, Guibas, Nguyen, Wang
    Proc. 2nd IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS) 2006, San Francisco
  14. (Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram
    Funke, Malamatos, Matijevic, Wolpert
    Proc. 18th Canadian Conference on Computational Geometry (CCCG) 2006, Kingston
  15. TRANSIT: Ultrafast Shortest-Path with Linear-Time Preprocessing
    Bast, Funke, Matijevic
    Proc. 9th DIMACS Implementation Challenge: The Shortest Path Problem 2006, Piscataway
  16. Energy-Aware Stage Illumination
    Eisenbrand, Funke, Karrenbauer, Matijevic
    to appear in International Journal of Computational Geometry and Applications (IJCGA) (invited paper)
    prelminary version also in Proc. 21st ACM Symposium on Computational Geometry (SoCG) 2005, Pisa
  17. Packing a Trunk - Now with a Twist!
    Eisenbrand, Funke, Karrenbauer, Reichel, Schoemer
    to appear in International Journal of Computational Geometry and Applications (IJCGA) (invited paper)
    preliminary version in Proc. ACM Symposium on Solid and Physical Modeling (SPM) 2005, Cambridge
    2nd place in Best Paper Award
  18. Approximating k-hop Minimum Spanning Trees
    Althaus, Funke, Har-Peled, Koenemann, Ramos, Skutella
    Operations Research Letters 2005 Vol. 33 (2), pages 115-120
  19. Controlled Perturbation for Delaunay Triangulations
    Funke, Klein, Mehlhorn, Schmitt
    Proc. of 16th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2005, Vancouver
  20. Infrastructure-Establishment from Scratch in Wireless Sensor Networks
    Funke, Milosavljevic
    1st IEEE International Conference on Distributed Computing in Sensor Systems (DCOSS) 2005, Marina del Rey
  21. A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs
    Funke, Kesselman, Meyer, Segal
    to appear in ACM Transactions on Sensor Networks
    preliminary version in Proc. 1st IEEE Int. Conf. on Wireless and Mobile Computing, Networking and Communications (WiMob) 2005, Montreal
  22. Topological Hole Detection in Wireless Sensor Networks and its Applications
    Funke
    3rd ACM/SIGMOBILE International Workshop on foundations of Mobile Computing (DIAL-M-POMC) 2005, Cologne
  23. Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks
    Funke, Matijevic, Sanders
    Proc. of AlgorithmS for Wireless And mobile Networks (A_SWAN) 2004, Boston
  24. Improved Approximation Algorithms for Connected Sensor Cover
    Funke, Kesselman, Lotker, Segal
    to appear in Wireless Networks
    preliminary version in Proc. of 3rd Int. Conf. on ADHOC Networks and Wireless (ADHOC-NOW) 2004, Vancouver, Canada
  25. Finding Planar Regions in a Terrain - In Practice and with a Guarantee
    Funke, Malamatos, Ray
    to appear in International Journal of Computational Geometry and Applications (invited paper)
    preliminary versions in Proc. 20th ACM Symposium on Computational Geometry (SoCG) 2004, New York
    Proc. 20th European Workshop on Computational Geometry (EWCG) 2004, Sevilla
  26. Point Containment in the Integer Hull of a Polyhedron
    Althaus, Eisenbrand, Funke, Mehlhorn
    Proc.15th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2004, New Orleans
  27. Packing a Trunk
    Eisenbrand, Funke, Reichel, Schoemer
    Proc. 11th Annual European Symposium on Algorithms (ESA) 2003, Budapest (Springer LNCS)
  28. Approximating Energy Efficient Paths in Wireless Multi-Hop Networks
    Funke, Matijevic, Sanders
    Proc. 11th Annual European Symposium on Algorithms (ESA) 2003, Budapest (Springer LNCS))
  29. Curve Reconstruction from Noisy Samples
    Cheng, Funke, Golin, Kumar, Poon, Ramos
    Computational Geometry - Theory and Applications (CGTA), Vol. 31, Issues 1-2 , May 2005, p. 63-100 (invited paper)
    preliminary version in Proc. 19th ACM Symposium on Computational Geometry (SoCG) 2003, San Diego
  30. Certifying and Repairing Solutions to Large LPs -- How Good are LP-Solvers ?
    Dhiflaoi, Funke, Kwappik, Mehlhorn, Seel, Schoemer, Schulte, Weber
    Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2003, Baltimore
  31. A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph
    Eisenbrand, Funke, Garg, Koenemann
    Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2003, Baltimore
  32. Smooth-Surface Reconstruction in Near-Linear Time
    Funke, Ramos
    Proc. 13th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2002, San Francisco
  33. A Separation Bound for Real Algebraic Expressions
    Burnikel, Funke, Mehlhorn, Schirra, Schmitt
    to appear in Algorithmica
    preliminary version in Proc. 9th Annual European Symposium on Algorithms (ESA) 2001, Arhus, Denmark (Springer LNCS)
  34. Surface Reconstruction in almost Linear Time under Locally Uniform Sampling
    Dey, Funke, Ramos
    Proc. 17th European Workshop on Computational Geometry (EWCG) 2001, Berlin
  35. Reconstructing Curves with Corners and Endpoints
    Funke, Ramos
    Proc. 12th ACM-SIAM Symposium on Discrete Algorithms (SODA) 2001, Washington DC
  36. LOOK -- A Lazy Object-Oriented Kernel for Geometric Computation
    Funke, Mehlhorn
    Computational Geometry - Theory and Applications (CGTA), Vol. 22, Issue 1-3, May 2002, p. 99-118 (invited paper)
    a preliminary version appeared in Proc. 16th ACM Symposium on Computational Geometry (SoCG) 2000, Hong Kong
  37. Structural Filtering -- A Paradigm for Efficient and Exact Geometric Programs
    Funke, Naeher, Mehlhorn
    to appear in Computational Geometry - Theory and Applications (CGTA) (invited paper)
    preliminary version in Proc. 11th Canadian Conference on Computational Geometry (CCCG) 1999, Vancouver
  38. Exact Geometric Predicates using Cascaded Computation
    Burnikel, Funke, Seel.
    International Journal of Computational Geometry and Applications (IJCGA), Vol. 11, No. 3 (2001) 245-266 (invited paper)
    a preliminary version appeared in Proc. 14th ACM Symposium on Computational Geometry (SoCG) 1998, Minneapolis

Publications of Stefan Funke (MPI database)