Daniel Dumitriu, Stefan Funke, Martin Kutz, Nikola Milosavljevic
it takes to Reconstruct a 2-Manifold in R 3
Infrastructure-Establishment from Scratch in Wireless Sensor Networks (2008)
Stefan Funke, Nikola Milosavljevic
Abstract. We present a distributed, localized and integrated approach for establishing both low-level (i.e. exploration of 1-hop neighbors, interference avoidance) and high-level (a subgraph of the...
General Terms Algorithms (2008)
Siu-wing Cheng, Hong Kong, Stefan Funke, Mordecai Golin, Edgar Ramos
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from n noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Stefan Funke, Christian Klein, Kurt Mehlhorn, Susanne Schmitt
Project co-funded by the European Commission within FP6 (2002–2006) under contract nr. IST-006413 Most geometric algorithms are idealistic in the sense that they are designed for the Real-RAM model...
(Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram (2008)
Stefan Funke, Theocharis Malamatos, Domagoj Matijevic, Nicola Wolpert
ABSTRACT Finding Planar Regions in a Terrain – In Practice and with a Guarantee ∗ (2008)
Stefan Funke, Theocharis Malamatos, Rahul Ray
We consider the problem of computing large connected regions in a triangulated terrain of size n for which the normals of the triangles deviate by at most some small fixed angle. In previous work an...
Abstract Smooth-Surface Reconstruction in Near-Linear Time (2008)
A surface reconstruction algorithm takes as input a set of sample points from an unknown closed and smooth surface in 3-d space, and produces a piece-wise linear approximation of the surface that...
Information Brokerage via Location-Free Double Rulings ⋆ (2008)
Abstract. The in-network aggregation and processing of information is what sets a sensor network apart from a pure data acquisition device. One way to model the exchange of information between the...
Friedrich Eisenbrand, Joachim Reichel, Stefan Funke
In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of...
Christoph Burnikel, Stefan Funke, Michael Seel
In this paper we talk about a new efficient numerical approach to deal with inaccuracy when implementing geometric algorithms. Using various floating-point filters together with arbitrary precision...
(Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram (2008)
Stefan Funke, Theocharis Malamatos, Domagoj Matijevic, Nicola Wolpert
Abstract Point Containment in the Integer Hull of a Polyhedron 1 (2008)
Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn
We show that the point containment problem in the integer hull of a polyhedron, which is defined by m inequalities, with coefficients of at most ϕ bits can be solved in time O(m + ϕ) in the...
ABSTRACT Hole Detection or: “How Much Geometry Hides in Connectivity?” (2008)
Wireless sensor networks typically consist of small, very simple network nodes without any positioning device like GPS. After an initialization phase, the nodes know with whom they can talk directly,...
Friedrich Eisenbr, Stefan Funke, Joachim Reichel, Elmar Schömer
Abstract. We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the...
Distance-Sensitive Information Brokerage in Sensor Networks (2008)
Stefan Funke, Leonidas J. Guibas, An Nguyen, Yusu Wang
Abstract. In a sensor network information from multiple nodes must usually be aggregated in order to accomplish a certain task. A natural way to view this information gathering is in terms of...
Distance-Sensitive Information Brokerage in Sensor Networks (2008)
Stefan Funke, Leonidas J. Guibas, Yusu Wang
Abstract. In a sensor network information from multiple nodes must usually be aggregated in order to accomplish a certain task. A natural way to view this information gathering is in terms of...
Abstract Certifying and Repairing Solutions to Large LPs (2008)
Marcel Dhiflaoui, Stefan Funke, Kurt Mehlhorn, Michael Seel, Elmar Schömer, ...
State-of-the-art linear programming (LP) solvers give solutions without any warranty. Solutions are not guaranteed to be optimal or even close to optimal. Of course, it is generally believed that the...
Project funded by the European Community under the “Information Society Technologies” (2008)
Stefan Funke, Edgar A. Ramos, Stefan Funkeý, Edgar A. Ramos
A surface reconstruction algorithm takes as input a set of sample points from an unknown closed and smooth surface in 3-d space, and produces a piece-wise linear approximation of the surface that...
Certifying and Repairing Solutions to Large LPs - How Good are LP-solvers? (2008)
Marcel Dhiflaoui, Carsten Kwappik, Stefan Funke, Kurt Mehlhorn, Michael Seel, ...
State-of-the-art linear programming (LP) solvers give solutions without any warranty. Solutions are not guaranteed to be optimal or even close to optimal. Of course, it is generally believed that the...
How much Geometry it takes to Reconstruct a 2-Manifold in R^3 (2008)
Dumitriu, Daniel, Funke, Stefan, Kutz, Martin, Milosavljevic, Nikola
Known algorithms for reconstructing a 2-manifold from a point sample in R3 are naturally based on deci- sions/predicates that take the geometry of the point sample into account. Facing the always...
On the Locality of Extracting a 2-Manifold in IR3 (2008)
Dumitriu, Daniel, Funke, Stefan, Kutz, Martin, Milosavljevic, Nikola
Algorithms for reconstructing a 2-manifold from a point sample in R^3 based on Voronoi-filtering like CRUST or CoCone still require -- after identifying a set of candidate triangles -- a so-called...
On the Locality of Extracting a 2-Manifold in R3 (2008)
Dumitriu, Daniel, Funke, Stefan, Kutz, Martin, Milosavljevic, Nikola
Energy-Aware Stage Illumination (2008)
Eisenbrand, Friedrich, Funke, Stefan, Karrenbauer, Andreas, Matijevic, Domagoj
Approximating Energy Ecient Paths in Wireless Multi-Hop Networks (2007)
Stefan Funke, Domagoj Matijevic, Peter S
Abstract. Given the positions of n sites in a radio network we consider the problem of nding routes between any pair of sites that minimize energy consumption and do not use more than some constant...
Tamal K. Dey, Stefan Funke, Edgar A. Ramos
We describe a new implementation of the COCONE algorithm for smooth surface reconstruction by Amenta et al. (2000). This implementation runs in O(n log n) time if the sample is "locally...
Tamal K. Dey, Stefan Funke, Edgar A. Ramos
We describe an implementation of the COCONE algorithm for smooth surface reconstruction which runs in O(n log n) time if the sample is "locally uniform " in addition to being good...
der Universität des Saarlandes (2007)
This thesis has two main parts. The first part deals with the problem of curve reconstruction. Given a finite sample set S from an unknown collection of curves Γ, the task is to compute the graph...
Tamal K. Dey, Stefan Funke, Edgar A. Ramos
We describe an implementation of the COCONE algorithm for smooth surface reconstruction which runs in O(n log n) time if the sample is "locally uniform " in addition to being good...
Certifying and Repairing Solutions to Large LPs - How Good are LP-solvers? (2007)
Marcel Dhiflaoui, Carsten Kwappik, Stefan Funke, Kurt Mehlhorn, Michael Seel, ...
State-of-the-art linear programming (LP) solvers give solutions without any warranty. Solutions are not guaranteed to be optimal or even close to optimal. Of course, it is generally believed that the...
Friedrich Eisenbrand, Stefan Funke, Joachim Reichel, Elmar Schömer
We report on a project with a German car manufacturer.
Guaranteed-delivery geographic routing under uncertain node locations (2007)
rely on exact location information at the nodes, because when the greedy routing phase gets stuck at a local minimum, they require, as a fallback, a planar subgraph whose identification, in all...
Improved approximation algorithms for connected sensor cover (2007)
Stefan Funke, Alex Kesselman, Zvi Lotker, Michael Segal
Abstract. Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery...
Improved approximation algorithms for connected sensor cover (2007)
Stefan Funke, Alex Kesselman, Fabian Kuhn, Zvi Lotker, Michael Segal
Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and...
Fast Routing in Road Networks using Transit Nodes (2007)
Bast, Holger, Funke, Stefan, Sanders, Peter, Schultes, Dominik
Information Brokerage Via Location-Free Double Rulings (2007)
The in-network aggregation and processing of information is what sets a sensor network apart from a pure data acquisition device. One way to model the exchange of information between the network...
Improved approximation algorithms for connected sensor cover (2007)
Funke, Stefan, Kesselman, Alexander, Kuhn, Fabian, Lotker, Zvi, Segal, Michael
Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets (2007)
We consider the problem of assigning powers to nodes of a wireless network in the plane such that a message from a source node s reaches all other nodes within a bounded number k of transmissions and...
In Transit to Constant Time Shortest-Path Queries in Road Networks (2007)
Bast, Holger, Funke, Stefan, Matijevic, Domagoj, Sanders, Peter, Schultes, Dominik
Power Assignment Problems in Wireless Communication (2006)
Funke, Stefan, Laue, Soeren, Lotker, Zvi, Naujoks, Rouven
A fundamental class of problems in wireless communication is concerned with the assignment of suitable transmission powers to wireless devices/stations such that the resulting communication graph...
Distance-sensitive routing and information brokerage in sensor networks (2006)
Stefan Funke, Leonidas J. Guibas, An Nguyen, Yusu Wang
Abstract — In a sensor network information from multiple nodes must usually be aggregated in order to accomplish a certain task. A natural way to view this information gathering is in terms of...
TRANSIT— ultrafast shortest-path queries with linear-time preprocessing (2006)
Holger Bast, Stefan Funke, Domagoj Matijevic
{bast,funke,dmatijev} at mpi-inf dot mpg dot de We introduce the concept of transit nodes, as a means for preprocessing a road network, with given coordinates for each node and a travel time for each...
Stefan Funke, Sören Laue, Lotker Rouven Naujoks, Stefan Funke, Rouven Naujoks, Lotker Zvi
A fundamental class of problems in wireless communication is concerned with the assignment of suitable transmission powers to wireless devices/stations such that the resulting communication graph...
TRANSIT— ultrafast shortest-path queries with linear-time preprocessing (2006)
Holger Bast, Stefan Funke, Domagoj Matijevic
{bast,funke,dmatijev} at mpi-inf dot mpg dot de We introduce the concept of transit nodes, as a means for preprocessing a road network, with given coordinates for each node and a travel time for each...
TRANSIT— ultrafast shortest-path queries with linear-time preprocessing (2006)
Holger Bast, Stefan Funke, Domagoj Matijevic
{bast,funke,dmatijev} at mpi-inf dot mpg dot de We introduce the concept of transit nodes, as a means for preprocessing a road network, with given coordinates for each node and a travel time for each...
(Approximate) Conic Nearest Neighbors and the induced Voronoi Diagram (2006)
Funke, Stefan, Malamatos, Theocharis, Matijevic, Domagoj, Wolpert, Nicola, Rappaport, David
For a given point set in Euclidean space we consider the problem of finding (approximate) nearest neighbors of a query point but restricting only to points that lie within a fixed cone with apex at...
Hole Detection or: "How Much Geometry Hides in Connectivity?" (2006)
Funke, Stefan, Klein, Christian, Amenta, Nina, Cheong, Otfried
Wireless sensor networks typically consist of small, very simple network nodes without any positioning device like GPS. After an initialization phase, the nodes know with whom they can talk directly,...
A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs (2006)
Funke, Stefan, Kesselman, Alexander, Meyer, Ulrich, Segal, Michael
Several routing schemes in ad hoc networks first establish a virtual backbone and then route messages via backbone nodes. One common way of constructing such a backbone is based on the construction...
TRANSIT: Ultrafast Shortest-Path Queries with Linear-Time Preprocessing (2006)
Bast, Holger, Funke, Stefan, Matijevic, Domagoj, Demetrescu, Camil, Goldberg, Andrew, Johnson, David
Distance-Sensitive Information Brokerage in Sensor Networks (2006)
Funke, Stefan, Guibas, Leonidas, Nguyen, An, Wang, Yusu, Gibbons, Phillip B., Abdelzaher, Tarek F., ...
In a sensor network information from multiple nodes must usually be aggregated in order to accomplish a certain task. A natural way to view this information gathering is in terms of interactions...
Approximating k-hop minimum-spanning trees (2005)
Althaus, Ernst, Funke, Stefan, Har-Peled, Sariel, Könemann, Jochen, A. Ramos, Edgar, Skutella, Martin
Given a complete graph on~n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Approximating k-hop minimum-spanning trees (2005)
Althaus, Ernst, Funke, Stefan, Har-Peled, Sariel, Könemann, Jochen, A. Ramos, Edgar, Skutella, Martin
Given a complete graph on~n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Packing a trunk - Now with a twist! (2005)
Eisenbrand, Friedrich, Funke, Stefan, Karrenbauer, Andreas, Reichel, Joachim, Schomer, Elmar
In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of...
Energy-aware stage illumination (2005)
Eisenbrand, Friedrich, Karrenbauer, Andreas, Funke, Stefan, Matijevic, Domagoj
Consider the following illumination problem: given a stage represented by a line segment L and a set of lightsources represented by a set of points S in the plane, assign powers to the lightsources...
Stefan Funke, Christian Klein, Kurt Mehlhorn, Susanne Schmitt
controlled perturbation, floating
A simple improved distributed algorithm for minimum cds in unit disk graphs (2005)
Stefan Funke, Er Kesselman, Ulrich Meyer, Michal Segal
Abstract — Several routing schemes in ad hoc networks first establish a virtual backbone and then route messages via backbone nodes. One common way of constructing such a backbone is based on the...
Approximation k-hop minimum-spanning trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-peled, Edgar A. Ramos, Martin Skutella
Abstract Given a complete graph on n nodes with metric edge costs, the minimum-cost k- hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest...
Approximating k-Hop Minimum-Spanning Trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos, Martin Skutella
Given a complete graph on n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Approximating k-Hop Minimum-Spanning Trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-Peled, Jochen Könemann, Edgar A. Ramos, Martin Skutella
Given a complete graph on n nodes with metric edge costs, the minimum-cost k-hop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
A simple improved distributed algorithm for minimum cds in unit disk graphs (2005)
Stefan Funke, Alex Kesselman, Ulrich Meyer, Michael Segal
1 We consider the problem of finding a minimum connected dominating set (CDS) in unit disk graphs. Algorithms for computing a small CDS are essential for efficient routing in ad hoc networks, where...
A simple improved distributed algorithm for minimum cds in unit disk graphs (2005)
Stefan Funke, Alex Kesselman, Ulrich Meyer, Michael Segal
1 We consider the problem of finding a minimum connected dominating set (CDS) in unit disk graphs. Algorithms for computing a small CDS are essential for efficient routing in ad hoc networks, where...
Approximation k-hop minimum-spanning trees (2005)
Ernst Althaus, Stefan Funke, Sariel Har-peled, Jochen Könemann, Edgar A. Ramos, Martin Skutella
Given a complete graph on n nodes with metric edge costs, the minimum-cost khop spanning tree (kHMST) problem asks for a spanning tree of minimum total cost such that the longest root-leaf-path in...
Energy-aware stage illumination (2005)
Friedrich Eisenbrand, Andreas Karrenbauer, Stefan Funke, Domagoj Matijevic
Consider the following illumination problem: given a stage represented by a line segment L and a set of lightsources represented by a set of points S in the plane, assign powers to the lightsources...
c ○ World Scientific Publishing Company Packing a Trunk – now with a Twist! (2005)
Friedrich Eisenbrand, Stefan Funke, Andreas Karrenbauer, Joachim Reichel, Elmar Schömer
Communicated by (Name) In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car...
Infrastructure-Establishment from Scratch in Wireless Sensor Networks (2005)
Funke, Stefan, Milosavljevic, Nikola, Prasanna, Viktor K., Iyengar, Sitharama, Spirakis, Paul, Welsh, Matt
Controlled Perturbation for Delaunay Triangulations (2005)
Funke, Stefan, Klein, Christian, Mehlhorn, Kurt, Schmitt, Susanne
Most geometric algorithms are idealistic in the sense that they are designed for the Real-RAM model of computation and for inputs in general position. Real inputs may be degenerate and floating point...
A Simple Improved Distributed Algorithm for Minimum CDS in Unit Disk Graphs (2005)
Funke, Stefan, Kesselmann, Alexander, Meyer, Ulrich, Segal, Michael
Packing a Trunk - now with a Twist! (2005)
Eisenbrand, Friedrich, Funke, Stefan, Karrenbauer, Andreas, Reichel, Joachim, Schömer, Elmar, Spencer, Stephen N.
In an industry project with a German car manufacturer we are faced with the challenge of placing a maximum number of uniform rigid rectangular boxes in the interior of a car trunk. The problem is of...
Energy-Aware Stage Illumination (2005)
Eisenbrand, Friedrich, Funke, Stefan, Karrenbauer, Andreas, Matijevic, Domagoj
Consider the following illumination problem: given a stage represented by a line segment $\Stage$ and a set of lightsources represented by a set of points $S$ in the plane, assign powers to the...
Approximating k-Hop Minimum-Spanning Trees (2005)
Althaus, Ernst, Funke, Stefan, Har-Peled, Sariel, Könemann, Jochen, Ramos, Edgar A., Skutella, Martin
In this paper we consider the problem of computing minimum-cost spanning trees with depth restrictions. Specifically, we are given an $n$-node complete graph $G$, a metric cost-function $c$ on its...
This thesis has two main parts. The first part deals with the problem of curve reconstruction. Given a finite sample set S from an unknown collection of curves Gamma, the task is to compute the graph...
Point containment in the integer hull of a polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks (2004)
Funke,Stefan, Matijevic,Domagoj, Sanders,Peter
We investigate algorithms for computing energy efficient paths in ad-hoc radio networks. We demonstrate how advanced data structures from computational geometry can be employed to preprocess the...
Improved Approximation Algorithms for Connected Sensor Cover (2004)
Funke,Stefan, Kesselmann,Alexander, Lotker,Zvi, Segal,Michael
Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and...
Point Containment in the Integer Hull of a Polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time...
The LEDA class real number - extended version (2004)
Funke,Stefan, Mehlhorn,Kurt, Schmitt,Susanne, Burnikel,Christoph, Fleischer,Rudolf, Schirra,Stefan
Point containment in the integer hull of a polyhedron (2004)
Althaus,Ernst, Eisenbrand,Friedrich, Funke,Stefan, Mehlhorn,Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Point containment in the integer hull of a polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks (2004)
Funke, Stefan, Matijevic, Domagoj, Sanders, Peter
We investigate algorithms for computing energy efficient paths in ad-hoc radio networks. We demonstrate how advanced data structures from computational geometry can be employed to preprocess the...
Improved Approximation Algorithms for Connected Sensor Cover (2004)
Funke, Stefan, Kesselmann, Alexander, Lotker, Zvi, Segal, Michael, Nikolaidis, Ioanis, Barbeau, Michel, ...
Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and...
Point Containment in the Integer Hull of a Polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time...
The LEDA class real number - extended version (2004)
Funke, Stefan, Mehlhorn, Kurt, Schmitt, Susanne, Burnikel, Christoph, Fleischer, Rudolf, Schirra, Stefan
Point containment in the integer hull of a polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time $O(m+\varphi)$...
Point containment in the integer hull of a polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
Constant time queries for energy efficient paths in multi-hop wireless networks (2004)
Stefan Funke, Domagoj Matijevic, Peter Sanders
Abstract — We investigate algorithms for computing en-ergy efficient paths in ad-hoc radio networks. We demon-strate how advanced data structures from computational geometry can be employed to...
Point containment in the integer hull of a polyhedron (2004)
Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn
We show that the point containment problem in the integer hull of a polyhedron, which is dened by m inequalities, with coecients of at most ' bits can be solved in time O(m + ') in the...
Point Containment in the Integer Hull of a Polyhedron (2004)
Althaus, Ernst, Eisenbrand, Friedrich, Funke, Stefan, Mehlhorn, Kurt
We show that the point containment problem in the integer hull of a polyhedron, which is defined by $m$ inequalities, with coefficients of at most $\varphi$ bits can be solved in time...
Improved Approximation Algorithms for Connected Sensor Cover (2004)
Funke, Stefan, Kesselmann, Alexander, Lotker, Zvi, Segal, Michael, Nikolaidis, Ioanis, Barbeau, Michel, ...
Wireless sensor networks have recently posed many new system building challenges. One of the main problems is energy conservation since most of the sensors are devices with limited battery life and...
Constant Time Queries for Energy Efficient Paths in Multi-Hop Wireless Networks (2004)
Funke, Stefan, Matijevic, Domagoj, Sanders, Peter
We investigate algorithms for computing energy efficient paths in ad-hoc radio networks. We demonstrate how advanced data structures from computational geometry can be employed to preprocess the...
Curve reconstruction from noisy samples (2003)
Cheng, Siu-Wing, Funke, Stefan, Golin, Mordecai J., Kumar, Piyush, Poon, Sheung-Hung, Ramos, Edgar A.
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Approximating Energy Efficient Paths in Wireless Multi-hop Networks (2003)
Funke,Stefan, Matijevic,Domagoj, Sanders,Peter
Given the positions of $n$ sites in a radio network we consider the problem of finding routes between any pair of sites that minimize energy consumption and do not use more than some constant number...
Certifying and Repairing Solutions to Large LPs - How Good are LP-Solvers? (2003)
Dhiflaoui,Marcel, Funke,Stefan, Kwappik,Carsten, Mehlhorn,Kurt, Seel,Michael, Schömer,Elmar, ...
Eisenbrand,Friedrich, Funke,Stefan, Reichel,Joachim, Schömer,Elmar
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to...
Eisenbrand,Friedrich, Funke,Stefan, Reichel,Joachim, Schömer,Elmar
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to...
Curve Reconstruction from Noisy Samples (2003)
Cheng,Siu-Wing, Funke,Stefan, Golin,Mordecai J., Kumar,Piyush, Poon,Sheung-Hung, Ramos,Edgar A.
A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph (2003)
Eisenbrand,Friedrich, Funke,Stefan, Garg,Naveen, Könemann,Jochen
A combinatorial algorithm for computing a maximum independent set in a t-perfect graph (2003)
Eisenbrand,Friedrich, Funke,Stefan, Garg,Naveen, Könemann,Jochen
We present a combinatorial polynomial time algorithm to compute a maximum stable set of a $t$-perfect graph. The algorithm rests on an $e$-approximation algorithm for general set covering and packing...
Approximating Energy Efficient Paths in Wireless Multi-hop Networks (2003)
Funke, Stefan, Matijevic, Domagoj, Sanders, Peter, Di Battista, Giuseppe, Zwick, Uri
Given the positions of $n$ sites in a radio network we consider the problem of finding routes between any pair of sites that minimize energy consumption and do not use more than some constant number...
Certifying and Repairing Solutions to Large LPs - How Good are LP-Solvers? (2003)
Dhiflaoui, Marcel, Funke, Stefan, Kwappik, Carsten, Mehlhorn, Kurt, Seel, Michael, Schömer, Elmar, ...
Eisenbrand, Friedrich, Funke, Stefan, Reichel, Joachim, Schömer, Elmar, Di Battista, Giuseppe, Zwick, Uri
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to...
Eisenbrand, Friedrich, Funke, Stefan, Reichel, Joachim, Schömer, Elmar, Di Battista, Giuseppe, Zwick, Uri
We report on a project with a German car manufacturer. The task is to compute (approximate) solutions to a specific large-scale packing problem. Given a polyhedral model of a car trunk, the aim is to...
Curve Reconstruction from Noisy Samples (2003)
Cheng, Siu-Wing, Funke, Stefan, Golin, Mordecai J., Kumar, Piyush, Poon, Sheung-Hung, Ramos, Edgar A.
A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph (2003)
Eisenbrand, Friedrich, Funke, Stefan, Garg, Naveen, Könemann, Jochen
A combinatorial algorithm for computing a maximum independent set in a t-perfect graph (2003)
Eisenbrand, Friedrich, Funke, Stefan, Garg, Naveen, Könemann, Jochen
We present a combinatorial polynomial time algorithm to compute a maximum stable set of a $t$-perfect graph. The algorithm rests on an $e$-approximation algorithm for general set covering and packing...
A combinatorial algorithm for computing a maximum independent set in a $t$-perfect graph (2003)
Eisenbrand, Friedrich, Funke, Stefan, Garg, Naveen, Könemann, Jochen
Curve Reconstruction from Noisy Samples (2003)
Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-hung Poon, Edgar Ramos
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Curve Reconstruction from Noisy Samples (2003)
Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-hung Poon, Edgar Ramos
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Curve Reconstruction from Noisy Samples (2003)
Siu-wing Cheng, Stefan Funke, Mordecai Golin, Piyush Kumar, Sheung-hung Poon, Edgar Ramos
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Approximating Energy Efficient Paths in Wireless Multi-Hop Networks (2003)
Stefan Funke, Domagoj Matijevic, Peter S
Abstract. Given the positions of n sites in a radio network we consider the problem of finding routes between any pair of sites that minimize energy consumption and do not use more than some constant...
Curve Reconstruction from Noisy Samples (2003)
Siu-Wing Cheng, Stefan Funke, Mordecai Golin, Piyush Kuma, Sheung-hung Poon, Edgar Ramos
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves...
Smooth-surface reconstruction in near-linear time (2002)
A surface reconstruction algorithm takes as input a set of sample points from an unknown closed and smooth surface in 3-d space, and produces a piece-wise linear approximation of the surface that...
Smooth-surface reconstruction in near-linear time (2002)
A surface reconstruction algorithm takes as input a set of sample points from an unknown closed and smooth surface in 3-d space, and produces a piece-wise linear approximation of the surface that...
A Combinatorial Algorithm for Computing a Maximum Independent Set in a t-perfect Graph (2002)
Friedrich Eisenbrand, Stefan Funke, Naveen Garg, Jochen Knemann
We present a combinatorial polynomial time algorithm to compute a maximum stable set of a t-perfect graph. The algorithm rests on an e-approximation algorithm for general set covering and packing...
Smooth-Surface Reconstruction in Near-Linear Time (2002)
A surface reconstruction algorithm takes as input a set of sample points from an unknown closed and smooth surface in 3-d space, and produces a piece-wise linear approximation of the surface that...
This thesis has two main parts. The first part deals with the problem of curve reconstruction. Given a finite sample set S from an unknown collection of curves Gamma, the task is to compute the graph...
Saarbrücken, University, Diss., 2001.
A separation bound for real algebraic expressions (2001)
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking...
Reconstructing a collection of curves with corners and endpoints (2001)
We present an algorithm which provably reconstructs a collection of curves with corners and endpoints from a sample set that satisfies a certain sampling condition. The algorithm outputs a polygonal...
A Separation Bound for Real Algebraic Expressions (2001)
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking...
A separation bound for real algebraic expressions (2001)
Christoph Burnikel, Stefan Funke, Kurt Mehlhorn, Stefan Schirra, Susanne Schmitt
Real algebraic expressions are expressions whose leaves are integers and whose internal nodes are additions, subtractions, multiplications, divisions, k-th root operations for integral k, and taking...
Reconstructing a collection of curves with corners and endpoints (2001)
We present an algorithm which provably reconstructs a collection of curves with corners and endpoints from a sample set that satisfies a certain sampling condition. The algorithm outputs a polygonal...
A Separation Bound for Real Algebraic Expressions (2001)
Burnikel, Christoph, Funke, Stefan, Mehlhorn, Kurt, Schirra, Stefan, Schmitt, Susanne
Exact Geometric Computation Using Cascading (2000)
Christoph Burnikel, Stefan Funke, Michael Seel
In this paper we talk about a new ecient numerical approach to deal with inaccuracy when implementing geometric algorithms. Using various oating-point lters together with arbitrary precision...
LOOK - A Lazy Object-Oriented Kernel for Geometric Computation (2000)
In this paper we describe and discuss a new kernel design for geometric computation in the plane. It combines different kinds of floating-point filter techniques and a lazy evaluation scheme with the...
In this paper we describe and discuss a new kernel design for geometric computation in the plane. It combines different kinds of floating-point filter techniques and a lazy evaluation scheme with the...
Structural filtering: A paradigm for efficient and exact geometric programs (1999)
Stefan Funke, Kurt Mehlhorn, Stefan Näher
We introduce a new filtering technique that can be used in the implementation of geometric algorithms called "structural filtering". Using this filtering techniques we gain about 20 % when...
Structural Filtering - A Paradigm for Efficient and Exact Geometric Programs (1999)
Stefan Funke, Kurt Mehlhorn, Stefan Näher
We introduce a new and simple filtering technique that can be used in the implementation of geometric algorithms called "structural filtering". Using this filtering technique we gain about...
Exact Geometric Predicates using Cascaded Computation (1998)
Christoph Burnikel, Stefan Funke, Michael Seel
In this paper we talk about a new efficient numerical approach to deal with inaccuracy when implementing geometric algorithms. Using various floating-point filters together with arbitrary precision...
Dresden, Med. Akad., Diss. A, 1989 (Nicht f.d. Austausch).
Beigeheftet 2 Sonderabdr. aus Verh. Dtsch. Ges. Path.