Polygon Exploration with Discrete Vision (2008)
Fekete, Sandor P., Schmidt, Christiane
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...
Staged Self-Assembly:Nanomanufacture of Arbitrary Shapes with O(1) Glues (2008)
Demaine, Erik D., Demaine, Martin L., Fekete, Sandor P., Ishaque, Mashhood, Rafalin, Eynat, Schweller, Robert T., ...
We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various...
Esther M. Arkin, Sandor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristan, ...
We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity (S) of S is given by the smallest number of reflex vertices...
A network-flow technique for finding low-weight bounded-degree trees (2007)
Sandor P. Fekete, Samir Khuller, Monika Klemmstein, Balaji Raghavachari, Neal Young
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at...
Extending Partial Suborders (2007)
We consider the problem of nding a transitive orientation T of a comparability graph G = (V; E), such that a given partial order P is extended. Existing algorithms for this problem require the full...
Submitted to JACM The Geometric Maximum Traveling Salesman Problem (2007)
Alexander Barvinok, Sandor P. Fekete, David S. Johnson, Arie Tamir, Gerhard J. Woeginger, Russell Woodroofe
We consider the traveling salesman problem when the cities are points in R
Sandor P. Fekete, Henk Meijer, Andre Rohe, Walter Tietze
Abstract. We consider geometric instances of the Maximum Weighted Matching Problem (MWMP) and the Maximum Traveling Salesman Problem (MTSP) with up to 3,000,000 vertices. Making use of a geometric...
Esther M. Arkin, Sandor P. Fekete, Ferran Hurtado, Marc Noy, Vera Sacristan, ...
We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity (S) of S is given by the smallest number of reflex vertices...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Saurabh Sethia
We give the first algorithmic study of a class of "covering tour " problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps...
Esther M. Arkin, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete, Saurabh Sethia
We give the rst algorithmic study of a class of \covering tour " problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps out a...
Minimizing the Stabbing Number of Matchings, Trees, and (2007)
Sandor P. Fekete, Marco E. Lubbecke, Henk Meijer
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...
On minimum stars, minimum Steiner stars, and maximum matchings (2007)
We discuss worst-case bounds on the ratio of maximum matching and minimum median values for nite point sets. In particular, we consider "minimum stars", which are dened by a center chosen...
An exact algorithm for higher-dimensional orthogonal packing (2006)
Fekete, Sandor P., Schepers, Joerg, Van Der Veen, Jan C.
Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Combining the use of our data structure for characterizing...
Locked and Unlocked Chains of Planar Shapes (2006)
Connelly, Robert, Demaine, Erik D., Demaine, Martin L., Fekete, Sandor P., Langerman, Stefan, Mitchell, Joseph S. B., ...
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...
Minimum-Cost Coverage of Point Sets by Disks (2006)
Arkin, Esther M., Broennimann, Herve, Erickson, Jeff, Fekete, Sandor P., Knauer, Christian, Lenchner, Jonathan, ...
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...
An exact algorithm for higher-dimensional orthogonal packing (2006)
Sandor P. Fekete, Jorg Schepers
Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Combining the use of our data structure for characterizing...
Deterministic boundary recognition and topology extraction for large sensor networks (2005)
Kroeller, Alexander, Fekete, Sandor P., Pfisterer, Dennis, Fischer, Stefan
We present a new framework for the crucial challenge of self-organization of a large sensor network. The basic scenario can be described as follows: Given a large swarm of immobile sensor nodes that...
DyNoC: A Dynamic Infrastructure for Communication in Dynamically Reconfigurable Devices (2005)
Bobda, Christophe, Ahmadinia, Ali, Majer, Mateusz, Teich, Juergen, Fekete, Sandor P., Van Der Veen, Jan
A new paradigm to support the communication among modules dynamically placed on a reconfigurable device at run-time is presented. Based on the network on chip (NoC) infrastructure, we developed a...
PackLib^2: An integrated library of multi-dimensional packing problems (2005)
Fekete, Sandor P., Van Der Veen, Jan
We present PackLib^2, the first fully integrated benchmark library for multi-dimensional packing instances. PackLib^2 combines a systematic collection of all benchmark instances from previous...
A New Approach for Boundary Recognition in Geometric Sensor Networks (2005)
Fekete, Sandor P., Kaufmann, Michael, Kroeller, Alexander, Lehmann, Katharina
We describe a new approach for dealing with the following central problem in the self-organization of a geometric sensor network: Given a polygonal region R, and a large, dense set of sensor nodes...
Defragmenting the Module Layout of a Partially Reconfigurable Device (2005)
Van Der Veen, Jan, Fekete, Sandor P., Ahmadinia, Ali, Bobda, Christophe, Hannig, Frank, Teich, Juergen
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 beforehand,...
A Practical Approach for Circuit Routing on Dynamic Reconfigurable Devices (2005)
Ahmadinia, Ali, Bobda, Christophe, Ding, Ji, Majer, Mateusz, Teich, Juergen, Fekete, Sandor P., ...
Management of communication by on-line routing in new FPGAs with a large amount of logic resources and partial reconfigurability is a new challenging problem. A Network-on-Chip (NoC) typically uses...
Koordinatenfreies Lokationsbewusstsein (Localization without Coordinates) (2005)
Kroeller, Alexander, Fekete, Sandor P., Buschmann, Carsten, Fischer, Stefan, Pfisterer, Dennis
Localization is one of the fundamental issues in sensor networks. It is almost always assumed that it must be solved by assigning coordinates to the nodes. This article discusses positioning...
Shawn: A new approach to simulating wireless sensor networks (2005)
Kroeller, Alexander, Pfisterer, Dennis, Buschmann, Carsten, Fekete, Sandor P., Fischer, Stefan
We consider the simulation of wireless sensor networks (WSN) using a new approach. We present Shawn, an open-source discrete-event simulator that has considerable differences to all other existing...
The one-round Voronoi game replayed (2005)
We consider the one-round Voronoi game, where the first player ("White", called "Wilma") places a set of n points in a rectangular area Q of aspect ratio r 1,...
Communication-Aware Processor Allocation for Supercomputers (2004)
Bender, Michael A., Bunde, David P., Demaine, Erik D., Fekete, Sandor P., Leung, Vitus J., Meijer, Henk, ...
This paper gives processor-allocation algorithms for minimizing the average number of communication hops between the assigned processors for grid architectures, in the presence of occupied cells. The...
Online Searching with Turn Cost (2004)
Demaine, Erik D., Fekete, Sandor P., Gal, Shmuel
We consider the problem of searching for an object on a line at an unknown distance OPT from the original position of the searcher, in the presence of a cost of d for each time the searcher changes...
Neighborhood-Based Topology Recognition in Sensor Networks (2004)
Fekete, Sandor P., Kroeller, Alexander, Pfisterer, Dennis, Fischer, Stefan, Buschmann, Carsten
We consider a crucial aspect of self-organization of a sensor network consisting of a large set of simple sensor nodes with no location hardware and only very limited communication range. After...
Online Searching with an Autonomous Robot (2004)
Fekete, Sandor P., Klein, Rolf, Nuechter, Andreas
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...
A General Framework for Bounds for Higher-Dimensional Orthogonal Packing Problems (2004)
Fekete, Sandor P., Schepers, Joerg
Higher-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. In the context of a branch-and-bound framework for solving...
The Freeze-Tag Problem: How to Wake Up a Swarm of Robots (2004)
Arkin, Esther M., Bender, Michael A., Fekete, Sandor P., Mitchell, Joseph S. B., Skutella, Martin
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 to their...
Communication-Aware Processor Allocation for Supercomputers (2004)
Michael A. Bender, David P. Bunde, Erik D. Demaine, Sandor P. Fekete, Vitus J. Leung, Henk Meijer, ...
hops between the assigned processors for grid architectures, in the presence of occupied cells. The simpler problem of assigning processors on a free grid has been studied by Karp, McKellar, and Wong...
Maximum dispersion and geometric maximum weight cliques (2003)
Fekete, Sandor P., Meijer, Henk
We consider a facility location problem, where the objective is to ``disperse'' a number of facilities, i.e., select a given number k of locations from a discrete set of n candidates, such that the...
A combinatorial characterization of higher-dimensional orthogonal packing (2003)
Fekete, Sandor P., Schepers, Joerg
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...
Minimizing the stabbing number of matchings, trees, and triangulations (2003)
Fekete, Sandor P., Luebbecke, Marco, Meijer, Henk
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. This paper deals with finding perfect...
On the continuous Fermat-Weber problem (2003)
Fekete, Sandor P., Mitchell, Joseph S. B., Beurer, Karin
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...
Optimal Covering Tours with Turn Costs (2003)
Arkin, Esther M., Bender, Michael A., Demaine, Erik D., Fekete, Sandor P., Mitchell, Joseph S. B., Sethia, Saurabh
We give the first algorithmic study of a class of ``covering tour'' problems related to the geometric Traveling Salesman Problem: Find a polygonal tour for a cutter so that it sweeps out a specified...
Higher-Dimensional Packing with Order Constraints (2003)
Fekete, Sandor P., Koehler, Ekkehard, Teich, Juergen
We present a first exact study on higher-dimensional packing problems with order constraints. Problems of this type occur naturally in applications such as logistics or computer architecture and can...
The one-round Voronoi game replayed (2003)
Fekete, Sandor P., Meijer, Henk
We consider the one-round Voronoi game, where player one (``White'', called ``Wilma'') places a set of n points in a rectangular area of aspect ratio r 2 and r>sqrt{2}/n, and for n=2 and r>sqrt{3}/2....
The complexity of economic equilibria for house allocation markets (2003)
Fekete,Sandor P., Skutella,Martin, Woeginger,Gerhard J.
We prove NP-completeness of deciding the existence of an economic equilibrium in so-called house allocation markets. House allocation markets are markets with indivisible goods in which every agent...
The complexity of economic equilibria for house allocation markets (2003)
Fekete, Sandor P., Skutella, Martin, Woeginger, Gerhard J.
We prove NP-completeness of deciding the existence of an economic equilibrium in so-called house allocation markets. House allocation markets are markets with indivisible goods in which every agent...
On the reflexivity of point sets (2003)
S Andor, P. Fekete, Esther M. Arkin, Esther M. Arkin, Sandor P. Fekete, Ferran Hurtado, ...
x We introduce a new measure for planar point sets S. Intuitively, it describes the combinatorial distance from a convex set: The reflexivity (S) of S is given by the smallest number of reflex...
What is the Optimal Shape of a City? (2003)
Carl M. Bender, Michael A. Bender, Erik D. Demaine, Sandor P. Fekete
If one de nes the distance between two points as the Manhattan distance (the sum of the horizontal distance along streets and the vertical distance along avenues) then one can de ne a city as being...
Minimizing The Stabbing Number Of Matchings, Trees, And Triangulations (2003)
Sandor P. Fekete, S Andor, P. Fekete, Marco E. LÜbbecke, Henk Meijer
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...
Characterizing Matchings as the Intersection of Matroids (2002)
Fekete, Sandor P., Firla, Robert T., Spille, Bianca
This paper deals with the problem of representing the matching independence system in a graph as the intersection of finitely many matroids. After characterizing the graphs for which the matching...
Fekete, Sandor P., Meijer, Henk, Rohe, Andre, Tietze, Walter
We consider geometric instances of the Maximum Weighted Matching Problem (MWMP) and the Maximum Traveling Salesman Problem (MTSP) with up to 3,000,000 vertices. Making use of a geometric duality...
Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments (2002)
Hsiang, Tien-Ruey, Arkin, Esther M., Bender, Michael, Fekete, Sandor P., Mitchell, Joseph S. B.
We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire...
Traveling Salesmen in the Presence of Competition (2002)
Fekete, Sandor P., Fleischer, Rudolf, Fraenkel, Aviezri, Schmitt, Matthias
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 of...
On the Reflexivity of Point Sets (2002)
Arkin, Esther M., Fekete, Sandor P., Hurtado, Ferran, Mitchell, Joseph S. B., Noy, Marc, Sacristan, Vera, ...
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 rho(S) of S is given by the smallest number of reflex...
An Algorithmic Study of Manufacturing Paperclips and Other Folded Structures (2002)
Arkin, Esther M., Fekete, Sandor P., Mitchell, Joseph S. B.
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...
The Geometric Maximum Traveling Salesman Problem (2002)
Barvinok, Alexander, Fekete, Sandor P., Johnson, David S., Tamir, Arie, Woeginger, Gerhard J., Woodroofe, Russ
We consider the traveling salesman problem when the cities are points in R^d for some fixed d and distances are computed according to geometric distances, determined by some norm. We show that for...
The freeze-tag problem: How to wake up a swarm of robots (2002)
Esther M. Arkin, Michael A. Bender, Sandor 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...
Algorithms for Rapidly Dispersing Robot Swarms in Unknown Environments (2002)
Tien-ruey Hsiang, Esther M. Arkin, Michael A. Bender, Sandor P. Fekete
We develop and analyze algorithms for dispersing a swarm of primitive robots in an unknown environment, R. The primary objective is to minimize the makespan, that is, the time to fill the entire...
New classes of fast lower bounds for bin packing problems (2001)
Sandor P. Fekete, Sandor P. Fekete, Tu Berlin, Or P. Fekete, J Org Schepers
New classes of fast lower bounds for bin packing problems by
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...
On minimum stars, minimum Steiner stars, and maximum matchings (2000)
Sandor P. Fekete, Henk Meijer, Henk Meijer
We discuss properties and values of maximum matchings and minimum median problems for finite point sets. In particular, we consider "minimum stars", which are defined by a center...
On the manufacturability of paperclips and sheet metal structures (1999)
Esther M. Arkin, Sandor P. Fekete, Steven S. Skiena
We consider an algorithmic problem that arises in the study of the manufacturability of sheet metal parts: Given a flat piece, F, of sheet metal (or cardboard, or other bendable "stiff...
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...
Compile-Time Optimization of Dynamic Hardware Reconfigurations (1999)
Jürgen Teich, Sandor P. Fekete, Jörg Schepers
Recent generations of Field Programmable Gate Arrays (FPGA) allow the dynamic reconfiguration of cells on the chip during run-time. For a given problem consisting of a set of tasks with computation...
New Classes of Lower Bounds for Bin Packing Problems (1998)
Sandor P. Fekete, S'andor P. Fekete, Jörg Schepers, Jorg Schepers
The bin packing problem is one of the classical NP-hard optimization problems. Even though there are many excellent theoretical results, including polynomial approximation schemes, there is still a...
Simplicity and Hardness of the Maximum Traveling Salesman Problem under Geometric Distances (1998)
Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete
Recently, Barvinok, Johnson, Woeginger, and Woodroofe have shown that the Maximum TSP, i. e., the problem of finding a traveling salesman tour of maximum length, can be solved in polynomial time,...
A note on the Traveling Preacher Problem (1998)
Or P. Fekete, Sandor P. Fekete, S'andor P. Fekete, William R. Pulleyblank, William R. Pulleyblank, William R. Pulleyblank
In this paper, we consider a problem of cost allocations for shortest roundtrips. Given a weighted graph G = (V; E), we are to find a subset S ` V with a maximum weight core element for the Traveling...
On Maximum Matchings and Minimum Stars (1998)
Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete, Henk Meijer, Henk Meijer, Henk Meijer
We discuss properties and values of maximum matchings and minimum median problems for finite point sets. In particular, we consider "minimum stars", which are defined by a choosing a...
Tree Spanners in Planar Graphs (1998)
Lehrstuhl Fur Volkswirtschaftslehre, Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete, Jana Kremer, Jana Kremer, ...
) S'andor P. Fekete 1 and Jana Kremer 2 1 Center for Parallel Computing, Universitat zu Koln D--50923 Koln, GERMANY sandor@zpr.uni-koeln.de 2 Lehrstuhl fur Volkswirtschaftslehre Otto-Friedrich...
Tree Spanners in Planar Graphs (1998)
Lehrstuhl Fur Volkswirtschaftslehre, Sandor P. Fekete, Sandor P. Fekete, Sandor P. Fekete, Jana Kremer, ...
. A tree t-spanner of a graph G is a spanning subtree T of G in which the distance between every pair of vertices is at most t times their distance in G. Spanner problems have received some...
The Complexity of an Inverse Shortest Paths Problem (1998)
Sandor P. Fekete, Or P. Fekete, Winfried Hochstättler, Winfried Hochstattler, Stephan Kromberg, Stephan Kromberg, ...
In this paper we study the complexity of an Inverse Shortest Paths Problem (ISPP). We show that the problem is intractable even in very restricted cases. In particular, we prove that the ISPP is...
Finding maximum length tours under Euclidean norms (1998)
Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete
Recently, Barvinok, Johnson, Woeginger, and Woodroofe have shown that the Maximum TSP, i. e., the problem of finding a traveling salesman tour of maximum length, can be solved in polynomial time,...
New Classes of Lower Bounds for Bin Packing Problems (1998)
Sandor P. Fekete, Jörg Schepers, Or P. Fekete, J Org Schepers
The bin packing problem is one of the classical NP-hard optimization problems. Even though there are many excellent theoretical results, including polynomial approximation schemes, there is still a...
A Network Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1997)
Sandor P. Fekete, S'andor P. Fekete, Samir Khuller, Samir Khuller, Monika Klemmstein, Monika Klemmstein, ...
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at...
The nucleon of cooperative games and an algorithm for matching games (1997)
Ulrich Faigle, Sandor P. Fekete, Winfried Hochstättler, Walter Kern
The nucleon is introduced as a new allocation concept for non-negative cooperative n-person transferable utility games. The nucleon may be viewed as the multiplicative analogue of Schmeidler's...
Approximation Algorithms for Lawn Mowing and Milling (1997)
Esther M. Arkin, Esther M. Arkin, Sandor P. Fekete, Sandor P. Fekete, ...
We study the problem of finding shortest tours/paths for "lawn mowing" and "milling" problems: Given a region in the plane, and given the shape of a "cutter" (typically,...
Geometric Ideas for Graph Representation and for Cooperative Game Theory (1997)
Sandor P. Fekete, Sandor P. Fekete
linear dependance in lattices. Amer. Journal of Mathematics, 57 (1935), pp. 800--804. [13] P. Bose, H. Everett, S. Fekete, A. Lubiw, H. Meijer, K. Romanik, T. Shermer, and S. Whitesides. On a...
On more-dimensional packing II: Bounds (1997)
Sandor P. Fekete, Jörg Schepers, Sandor P. Fekete, Sandor P. Fekete
More-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. In the context of a branchand -bound framework for solving these...
Rendezvous Search on the Plane (1997)
Edward J. Anderson, Sandor P. Fekete
We consider rendezvous problems in which two players move on the plane and wish to cooperate in order to minimise their first meeting time. We begin by considering the case when they know that they...
On more-dimensional packing I: Modeling (1997)
Sandor P. Fekete, Jörg Schepers, Sandor P. Fekete, Sandor P. Fekete
More-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Previous eorts for exact algorithms have been unable to avoid...
Approximation of Geometric Dispersion Problems (1997)
Sandor P. Fekete, Christoph Baur, Christoph Baur, Christoph Baur, Or P. Fekete
) Christoph Baur and S'andor P. Fekete Center for Parallel Computing, Universitat zu Koln, D--50923 Koln, Germany [baur,fekete]@zpr.uni-koeln.de Abstract. We consider problems of distributing a...
On more-dimensional packing III: Exact Algorithms (1997)
Sandor P. Fekete, Jörg Schepers, Sandor P. Fekete, Sandor P. Fekete
More-dimensional orthogonal packing problems have a wide range of practical applications, including packing, cutting, and scheduling. Combining the use of our data structure for characterizing...
Approximation Algorithms for Lawn Mowing and Milling (1997)
Esther M. Arkin, Esther M. Arkin, Sandor P. Fekete, Sandor P. Fekete, ...
We study the problem of finding shortest tours/paths for "lawn mowing" and "milling" problems: Given a region in the plane, and given the shape of a "cutter" (typically,...
On a Visibility Representation of Graphs in 3D (1997)
Prosenjit Bose, Hazel Everett, Hazel Everett, Sandor P. Fekete, S'andor P. Fekete, Michael E. Houle, ...
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...
Histogram decomposition and stereolithography (1997)
A polyhedral solid model can be constructed by the process of stereolithography if it has a facet so that all points of the model can see this facet, in the direction orthogonal to it; such a...
Traveling Salesmen in the Age of Competition (1997)
Sandor P. Fekete, S'andor P. Fekete, Matthias Schmitt, Matthias Schmitt
) S'andor P. Fekete Matthias Schmitt Center for Parallel Computing Universitat zu Koln D -- 50931 Koln, Germany E-Mail: sandor@zpr.uni-koeln.de mschmitt@zpr.uni-koeln.de Abstract We propose the...
Traveling the Boundary of Minkowski Sums (1997)
Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete, William R. Pulleyblank, William R. Pulleyblank, William R. Pulleyblank
We consider the problem of traveling the contour of the set of all points that are within distance 1 of a connected planar curve arrangement P, forming an embedding of the graph G. We show that if...
Traveling the Boundary of Minkowski Sums (1997)
Sandor P. Fekete, William R. Pulleyblank
We consider the problem of traveling the contour of the set of all points that are within distance 1 of a connected planar curve arrangement P, forming an embedding of the graph G. We show that if...
Area optimization of simple polygons (1997)
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...
Histogram Decomposition and Stereolithography (1997)
Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete
A polyhedral solid model can be constructed by the process of stereolithography if it has a facet so that all points of the model can see this facet, in the direction orthogonal to it; such a...
Approximation Algorithms for Lawn Mowing and Milling (1997)
Esther M. Arkin, Esther M. Arkin, Esther M. Arkin, Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete, ...
We study the problem of finding shortest tours/paths for "lawn mowing" and "milling" problems: Given a region in the plane, and given the shape of a "cutter" (typically,...
A New Exact Algorithm for General Orthogonal D-Dimensional Knapsack Problems (1997)
Sandor P. Fekete, S'andor P. Fekete, Or P. Fekete, Jörg Schepers, Jorg Schepers, Jorg Schepers
The d-dimensional orthogonal knapsack problem (OKP) has a wide range of practical applications, including packing, cutting, and scheduling. We present a new approach to this problem, using a...
Angle-Restricted Tours in the Plane (1996)
Sandor P. Fekete, S'andor P. Fekete, Or P. Fekete, Gerhard J. Woeginger, Gerhard J. Woeginger, Gerhard J. Woeginger
For a given set A ` (\Gamma; +] of angles, the problem "Angle-Restricted Tour" (ART) is to decide whether a set P of n points in the Euclidean plane allows a closed directed tour consisting...
New Results on a Visibility Representation of Graphs in 3D (1996)
Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete, Michael E. Houle, Michael E. Houle, Michael E. Houle, ...
This paper considers a 3-dimensional visibility representation of cliques K n . In this representation, the objects representing the vertices are 2dimensional and lie parallel to the x; y-plane, and...
Rectangle and Box Visibility Graphs in 3D (1996)
Sandor P. Fekete, S'andor P. Fekete, S Andor, P. Fekete, Henk Meijer, Henk Meijer, ...
We discuss rectangle and box visibility representations of graphs in 3-dimensional space. In these representations, vertices are represented by axis-aligned disjoint rectangles or boxes. Two vertices...
On approximately fair cost allocation in Euclidean TSP games (1996)
U. Faigle, S. Fekete, W. Hochstattler, Walter Kern, Sandor 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...
New Results on a Visibility Representation of Graphs in 3D (1996)
Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete, Michael E. Houle, Michael E. Houle, Michael E. Houle, ...
This paper considers a 3-dimensional visibility representation of cliques K n . In this representation, the objects representing the vertices are 2dimensional and lie parallel to the x; y-plane, and...
Angle-Restricted Tours in the Plane (1996)
Sandor P. Fekete, S'andor P. Fekete, Or P. Fekete, Gerhard J. Woeginger, Gerhard J. Woeginger, Gerhard J. Woeginger
For a given set A ` (\Gammaß
A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1995)
Fekete, Sandor P., Khuller, Samir, Klemmstein, Monika, Raghavachari, Balaji, Young, Neal
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at...
A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1995)
Fekete, Sandor P., Khuller, Samir, Klemmstein, Monika, Raghavachari, Balaji, Young, Neal
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at...
Finding All Anchored Squares in a Convex Polygon in Subquadratic Time (1995)
Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete
We present an O(n log 2 n) method that finds all squares inscribed in a convex polygon with n vertices such that at least one corner lies on a vertex of the polygon. Keywords: Computational geometry,...
Finding All Anchored Squares in a Convex Polygon in Subquadratic Time (1995)
Sandor P. Fekete, S'andor P. Fekete, S'andor P. Fekete
We present an O(n log 2 n) method that finds all squares inscribed in a convex polygon with n vertices such that at least one corner lies on a vertex of the polygon. Keywords: Computational geometry,...
Worst-Case Ratios for Degree-Constrained Trees (1995)
Sandor P. Fekete, S'andor P. Fekete, Monika Klemmstein, Monika Klemmstein
We discuss problems of minimum degree-constrained trees T k , where each vertex of a complete graph Kn with a metric satifying triangle inequality is restricted to at most k neighbors. We show that...
A Network-Flow Technique for Finding Low-Weight Bounded-Degree Spanning Trees (1995)
Sandor P. Fekete, Samir Khuller, Monika Klemmstein, Neal Young, Balaji Raghavachari, Balaji Raghavachari
Given a graph with edge weights satisfying the triangle inequality, and a degree bound for each vertex, the problem of computing a low weight spanning tree such that the degree of each vertex is at...
On a Visibility Representation for Graphs in Three Dimensions (1995)
Prosenjit Bose, Qu'ebec Ga H, Hazel Everett, Hazel Everett, Sandor P. Fekete, S'andor P. Fekete, ...
Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit...
On The Complexity Of Testing Membership In The Core Of Min-Cost Spanning Tree Games (1994)
U. Faigle, S. Fekete, W. Hochstattler, Walter Kern, Sandor P. Fekete, Winfried Hochstättler, ...
Let N = f1, ..., ng be a finite set of players and KN the complete graph on the node set N [ f0g. Assume that the edges of KN have nonnegative weights and associate with each coalition S ` N of...
On a Visibility Representation for Graphs in Three Dimensions (1993)
Prosenjit Bose, Hazel Everett, Sandor P. Fekete, Anna Lubiw, Henk Meijer, Kathleen Romanik, ...
Visibility representations of graphs map vertices to sets in Euclidean space and express edges as visibility relations between these sets. Application areas such as VLSI wire routing and circuit...
A Note on the Traveling Preacher Problem
Sandor P. Fekete, William R. Pulleyblank
In this paper, we consider a problem of cost allocations for shortest roundtrips. Given a weighted graph G = (V; E), we are to nd a subset S V with a maximum weight core element for the Traveling...