Searching with an autonomous robot, in (2009)
Sándor P. Fekete, Rolf Klein, Andreas Nüchter
Abstract. We discuss online strategies for visibility-based searching for an object hidden behind a corner, using Kurt3D, a real autonomous mobile robot. This task is closely related to a number of...
Improved Approximation Algorithms for Relay Placement (2009)
Alon Efrat, Sándor P. Fekete, A R. Gaddehosur, Valentin Polishchuk, Jukka Suomela
Abstract. In the relay placement problem the input is a set of sensors and a number r ≥ 1, the communication range of a relay. In the one-tier version of the problem the objective is to place a...
A combinatorial characterization of higher-dimensional orthogonal packing (2009)
Sándor P. Fekete, Jörg Schepers
Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Previous efforts for exact algorithms have been unable to avoid...
Robert Connelly, Sándor P. Fekete, Tu Braunschweig, Erik D. Demaine, ...
We extend linkage unfolding results from the well-studied case of polygonal linkages to the more general case of linkages of polygons. More precisely, we consider chains of nonoverlapping rigid...
Sándor P. Fekete, Tu Braunschweig, Henk Meijer, André Rohe, Walter Tietze, ...
An extended abstract appears in the proceedings of ALENEX’01 [Fekete et al. 2001].
SpyGlass: A Wireless Sensor Network Visualizer (2008)
Carsten Buschmann, Dennis Pfisterer, Stefan Fischer, Sándor P. Fekete, Alexander Kröller
In this paper we present a modular and extensible visualization framework for wireless sensor networks. These networks have typically no means of visualizing their internal state, sensor readings or...
ABSTRACT Minimum-Cost Coverage of Point Sets by Disks ∗ (2008)
Helmut Alt, Jeff Erickson, Jonathan Lenchner, Esther M. Arkin, Sándor P. Fekete
We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t j) and radii (r j) that cover a given set of demand points Y...
General Terms Autonomous vehicles (2008)
Sándor P. Fekete, Tu Braunschweig
competitive ratio, three-dimensional laser scanning, autonomous mobile robots, Kurt3D. 1.
Sándor P. Fekete, Christiane Schmidt, Tu Braunschweig
With the advent of autonomous robots with two- and three-dimensional scanning capabilities, classical visibility-based exploration methods from computational geometry have gained in practical...
Sándor P. Fekete, Diana Göhringer
In this paper, we present an approach for simultaneous scheduling and placement of communicating modules for SoC architectures including devices with partial reconfiguration support and at least one...
General Terms Algorithms (2008)
Sándor P. Fekete, Tu Braunschweig
competitive ratio, three-dimensional laser scanning, autonomous mobile robots, Kurt3D. 1.
Abstract Minimizing the Stabbing Number of Matchings, Trees, and (2008)
Sándor P. Fekete, Marco E. Lübbecke
The (axis-parallel) stabbing number of a given set of line segments is the maximum number of segments that can be intersected by any one (axis-parallel) line. We investigate problems of finding...
Robert Connelly, Sándor P. Fekete, Tu Braunschweig, Erik D. Demaine, ...
We extend linkage unfolding results from the well-studied case of polygonal linkages to the more general case of linkages of polygons. More precisely, we consider chains of nonoverlapping rigid...
Poster Abstract: SpyGlass: Taking a closer look at Sensor Networks (2008)
Carsten Buschmann, Sándor P. Fekete
In this paper we present a modular and extensible visualization framework for wireless sensor networks. These networks have typically no means of visualizing their state, measurements or...
Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Martin Skutella
Abstract. An optimization problem that naturally arises in the study of swarm robotics is the Freeze-Tag Problem (FTP) of how to awaken a set of “asleep ” robots, by having an awakened robot move...
Online Dispersion Algorithms for Swarms of Robots (2007)
Tien-ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sándor P. Fekete
We illustrate algorithms for dispersing a swarm of primitive robots in a two-dimensional unknown environment R. Each robot in the swarm is equipped with a very simple sensor that is able to query the...
On rolling cube puzzles (2007)
Kevin Buchin, Maike Buchin, Erik D. Demaine, Martin L. Demaine, Dania El-khechen, Sándor P. Fekete, ...
We analyze the computational complexity of various rolling cube puzzles. 1
Locked and unlocked chains of planar shapes (2006)
Robert Connelly, Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Stefan Langerman, ...
We extend linkage unfolding results from the well-studied case of polygonal linkages to the more general case of linkages of polygons. More precisely, we consider chains of nonoverlapping rigid...
Minimizing communication cost for reconfigurable slot modules (2006)
We discuss the problem of communication-aware module placement in array-like reconfigurable environments, such as the Erlangen Slot Machine (ESM). Bad placement of modules may degrade performance due...
Minimum-cost coverage of point sets by disks (2006)
Helmut Alt, Esther M. Arkin, Hervé Brönnimann, Jeff Erickson, Sándor P. Fekete, Christian Knauer, ...
We consider a class of geometric facility location problems in which the goal is to determine a set X of disks given by their centers (t j) and radii (r j) that cover a given set of demand points Y...
Communication-aware processor allocation for supercomputers (2005)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, ...
Abstract. We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of...
Communication-aware processor allocation for supercomputers (2005)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, ...
Abstract. We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of...
Defragmenting the module layout of a partially reconfigurable device (2005)
Sándor P. Fekete, Mateusz Majer, Ali Ahmadinia, Christophe Bobda, Frank Hannig, ...
Abstract — Modern generations of field-programmable gate arrays (FPGAs) allow for partial reconfiguration. In an online context, where the sequence of modules to be loaded on the FPGA is unknown...
The Erlangen Slot Machine: A highly flexible FPGA-based reconfigurable platform (2005)
Christophe Bobda, Mateusz Majer, Ali Ahmadinia, Thomas Haller, André Linarth, Jürgen Teich, ...
We present a new concept as well as the implementation of an FPGA-based reconfigurable platform, the Erlangen Slot Machine (ESM). The main advantages of this platform are: first, the possibility for...
Communication-aware processor allocation for supercomputers (2005)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sándor P. Fekete, Vitus J. Leung, Henk Meijer, ...
Abstract. We give processor-allocation algorithms for grid architectures, where the objective is to select processors from a set of available processors to minimize the average number of...
Traveling Salesmen in the Presence of Competition (2004)
Sándor P. Fekete, Rudolf Fleischer, Aviezri Fraenkel, Matthias Schmitt
We propose the \Competing Salesmen Problem" (CSP), a 2-player competitive version of the classical Traveling Salesman Problem. This problem arises when considering two competing salesmen instead...
Optimal routing-conscious dynamic placement for reconfigurable computing (2004)
Ali Ahmadinia, Christophe Bobda, Sándor P. Fekete, Jürgen Teich
We describe algorithmic results for two crucial aspects of allocating resources on computational hardware devices with partial reconfigurability. By using methods from the field of computational...
Optimal routingconscious dynamic placement for reconfigurable computing (2004)
Ali Ahmadinia, Christophe Bobda, Sándor P. Fekete, Jürgen Teich
Abstract. We describe algorithmic results for two crucial aspects of allocating resources on computational hardware devices with partial reconfigurability. By using methods from the field of...
Online searching with an autonomous robot (2004)
Sándor P. Fekete, Rolf Klein, Andreas Nüchter
Summary. We discuss online strategies for visibility-based searching for an object hidden behind a corner, using Kurt3D, a real autonomous mobile robot. This task is closely related to a number of...
On the reflexivity of point sets (2003)
Esther M. Arkin, Sándor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristán, ...
We introduce a new measure for planar point sets S that captures a combinatorial distance that S is from being a convex set: The reflexivity ρ(S) ofS is given by the smallest number of reflex...
An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures (2003)
Esther M. Arkin, Sándor P. Fekete, Or P. Fekete
We study algorithmic aspects of bending wires and sheet metal into a specified structure. Problems of this type are closely related to the question of deciding whether a simple non-self-intersecting...
On the reflexivity of point sets (2003)
Esther M. Arkin, Sándor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristán, ...
Abstract. We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity ρ(S) ofS is given by the smallest number of...
The Freeze-Tag Problem: How to Wake Up a Swarm of Robots (2002)
Esther M. Arkin, Michael A. Bender, Sándor P. Fekete, Martin Skutella
An optimization problem that naturally arises in the study of "swarm robotics" is to wake up a set of "asleep" robots, starting with only one "awake" robot. One robot...
Optimal FPGA Module Placement with Temporal Precedence Constraints (2001)
We consider the optimal placement of hardware modules in space and time for FPGA architectures with reconfiguration capabilities, where modules are modeled as three-dimensional boxes in space and...
Optimal FPGA Module Placement with Temporal Precedence Constraints (2001)
We consider the optimal placement of hardware modules in space and time for FPGA architectures with reconfiguration capabilities, where modules are modeled as three-dimensional boxes in space and...
Continuous Weber and k-Median Problems (2000)
Karin Weinbrecht, Karin Weinbrecht, Sándor P. Fekete, Sandor P. Fekete, Sandor P. Fekete, ...
We give the first exact algorithmic study of facility location problems that deal with finding a median for a continuum of demand points. In particular, we consider versions of the "continuous...
Approximation of Geometric Dispersion Problems (1999)
Christoph Baur, Christoph Baur, Christoph Baur, Sándor P. Fekete, Sandor P. Fekete, Sandor P. Fekete, ...
We consider problems of distributing a number of points within a polygonal region P , such that the points are "far away" from each other. Problems of this type have been considered before...
On Simple Polygonizations with Optimal Area (1999)
Sándor P. Fekete, Sandor P. Fekete, Sandor P. Fekete
We discuss the problem of nding a simple polygonalization for a given set of vertices P that has optimal area. We show that these problems are very closely related to problems of optimizing the...
Fekete, Sándor P., Houle, Michael E., Whitesides, Sue
The logic engine technique has been used in the past to establish the NP-hardness of a number of graph representations. The original technique can only be applied in those situations in which...
Fekete, Sándor P., Houle, Michael E., Whitesides, Sue
The logic engine technique has been used in the past to establish the NP-hardness of a number of graph representations. The original technique can only be applied in those situations in which...
Fekete, Sándor P., Houle, Michael E., Whitesides, Sue
The logic engine technique has been used in the past to establish the NP-hardness of a number of graph representations. The original technique can only be applied in those situations in which...
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Sándor P. Fekete, Michael E. Houle, Anna Lubiw, Henk Meijer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V,E) in which vertices are mapped to rectangles floating in R 3 parallel to the x, y-plane, with edges represented by...
On a visibility representation for graphs in three dimensions (1998)
Prosenjit Bose, Hazel Everett, Sándor P. Fekete, Michael E. Houle, Anna Lubiw, Henk Meijer, ...
This paper proposes a 3-dimensional visibility representation of graphs G = (V,E) in which vertices are mapped to rectangles floating in R 3 parallel to the x, y-plane, with edges represented by...
Sándor P. Fekete, S'andor P. Fekete, Michael E. Houle, Michael E. Houle, Michael E. Houle, Sue Whitesides, ...
In this paper we describe a general technique for establishing NPhardness of graph representations. This technique is a generalization of the tool called the logic engine. We show that it is possible...
Area Optimization of Simple Polygons (1997)
Sándor P. Fekete, S'andor P. Fekete, S'andor P. Fekete
We discuss problems of optimizing the area of a simple polygon for a given set of vertices P and show that these problems are very closely related to problems of optimizing the number of points from...
New Results on a Visibility Representation of Graphs in 3D (1996)
Fekete, Sándor P., Houle, Michael E., Whitesides, Sue
This paper considers a 3-dimensional visibility representation of cliques K_n. In this representation, the objects representing the vertices are 2-dimensional and lie parallel to the x, y-plane, and...
New Results on a Visibility Representation of Graphs in 3D (1996)
Fekete, Sándor P., Houle, Michael E., Whitesides, Sue
This paper considers a 3-dimensional visibility representation of cliques K_n. In this representation, the objects representing the vertices are 2-dimensional and lie parallel to the x, y-plane, and...
New Results on a Visibility Representation of Graphs in 3D (1996)
Fekete, Sándor P., Houle, Michael E., Whitesides, Sue
This paper considers a 3-dimensional visibility representation of cliques K_n. In this representation, the objects representing the vertices are 2-dimensional and lie parallel to the x, y-plane, and...
On approximately fair cost allocation in Euclidean TSP games (1996)
U. Faigle, S. Fekete, W. Hochstattler, Walter Kern, Sándor P. Fekete, Winfried Hochstättler, ...
: We consider the problem of allocating the cost of an optimal traveling salesman tour in a fair way among the nodes visited; in particular, we focus on the case where the distance matrix of the...
Michael A. Bender, Sándor P. Fekete, Er Kröller, Valentin Polishchuk
Abstract. We introduce and study the minimum-backlog problem (MBP). The MBP arises in sensor networks and is related to the classic k-server problem. It can be understood as a 2-person game played on...
Robert T. Firla, Gutachter Prof, Dr. Robert Weismantel, Prof Dr, Alexander Martin, Prof Dr, ...
doctor rerum naturalium
On the Complexity of Testing Membership in the Core of Min-Cost Spanning Tree Games
Ulrich Faigle, Walter Kern, Winfried Hochstättler, Sándor P. Fekete
Let $N=\{ 1,...,n\} $ be a finite set of players and $K_{N}$ the complete graph on the node set $N\cup \{ 0\} $. Assume that the edges of $K_{N}$ have nonnegative weights and associate with each...