We consider a class of optimization problems that are fundamental to testing in modern configurable software systems, e.g., in automotive industries. In pairwise interaction sampling, we are given a (potentially very large) configuration space, in which each dimension corresponds to a possible Boolean feature of a software system; valid configurations are the satisfying assignments of a given propositional formula \(\unicode{x03C6}\). The objective is to find a minimum-sized family of configurations, such that each pair of features is jointly tested at least once. Due to its relevance in Software Engineering, this problem has been studied extensively for over 20 years.

Motivated by targeted drug delivery, we investigate the gathering of particles in the full tilt model of externally controlled motion planning: A set of particles is located at the tiles of a polyomino with all particles reacting uniformly to an external force by moving as far as possible in one of the four axis-parallel directions until they hit the boundary. The goal is to choose a sequence of directions that moves all particles to a common position. Our results include a polynomial-time algorithm for gathering in a completely filled polyomino as well as hardness reductions for approximating shortest gathering sequences and for determining whether the particles in a partially filled polyomino can be gathered. We pay special attention to the impact of restricted geometry, particularly polyominoes without holes. As a corollary, we make progress on an open question from [Balanza-Martinez et al., SODA 2020] by showing that deciding whether a given position can be occupied remains NP-hard in polyominoes without holes. Our results build on a connection we establish between tilt models and the theory of synchronizing automata.

A common sensing problem is to use a set of stationary tracking locations to monitor a collection of moving devices. Given n objects that need to be tracked, each following its own trajectory, and m stationary traffic control stations, each with a sensing region that can be changed over time; how should we adjust the individual sensor ranges in order to optimize energy consumption? We illustrate how to combine geometric insights with mathematical optimization to find optimal solutions for the min max variant of the problem, which aims at minimizing peak power consumption. Instances with 500 moving objects and 25 stations can be solved in the order of seconds for scenarios that take minutes to play out in the real world, demonstrating real-time capability of our methods.

The weak visibility polygon of a line segment s inside a simple polygon P, denoted by V_P(s), is the region of the polygon that is visible from at least one point on s. Given its fundamental nature in computational geometry, several algorithms have been proposed to compute weak visibility polygons efficiently, each with different trade-offs in terms of preprocessing time, query time, and space complexity. Although there are many applications that require computing these polygons such as computer graphics, robot motion planning, and network communication systems, there is a lack of any implementations of these algorithms in the literature - not to mention one that is exact, robust, and scalable. Furthermore, weak segment visibility polygons are used as basic building blocks in several other algorithms, such as in minimum-link path computation. In this work, we present an implementation of an optimal linear-time algorithm for computing the weak visibility polygon of a segment inside a triangulated simple polygon. Our implementation provides exact, robust geometric primitives and optimizations to handle large inputs with more than 18,000,000 vertices. We demonstrate two concrete applications: (1) construction of window partitions, a standard data structure in visibility algorithms, and (2) support for optimal minimum-link path queries between two points in a simple polygon, the latter serving as a direct use case of the former. Experimental results on a variety of polygon families confirm that the end-to-end running time scales linearly with the size of the polygon and is dominated by the cost of computing the triangulation, validating the practicality and scalability of the approach. The implementation is released as open source in the format of a CGAL package to support reproducibility and further research.

The Traveling Salesman Problem with Neighborhoods (TSPN) generalizes the classical Traveling Salesman Problem (TSP) by requiring a tour to visit a set of polygonal regions rather than fixed points, a natural goal that arises in various applications. While the geometric TSP allows arbitrarily close approximation and provably optimal solutions for benchmark instances of significant size, the TSPN is considerably more challenging, both in theory (due to APX-hardness) and practice, for which only benchmark instances up to 16 regions have been solved to optimality. Here we present a branch-and-bound algorithm that combines a spectrum of geometry-based filters (for reducing the number of considered sequences) with Second-Order Cone Programs (SOCP) (for computing optimal tours for a given permutation of neighborhoods). This allows us to solve larger polygonal TSPN instances than before to within an optimality tolerance of 0.1%; moreover, while previous work (both in theory and practice) relied on relatively benign neighborhoods, we can handle non-convex, non-simple neighborhoods of different sizes. In experiments on 490 benchmark instances with up to 50 polygons each, our method achieves a 99.6% optimality rate within 300s, with the remaining two instances solved within 595s. For 68 larger instances of size n = 60, our method still allows solving 86.8% of instances to optimality within 900s, leaving only 3 of the instances with optimality gaps above 3%, with the maximum being 5.53%.

We motivate and demonstrate simulation and evaluation of large-scale, fine-grained hydrodynamic flows, triggered by heavy-rain events. We show significant progress for simulating time-dependent, high-resolution runoff in large-scale heavy-rain scenarios, based on different geometry-based algorithmic speedup techniques. This enables us to address a second challenge: How can we deal with the instability of precipitation events, which are notoriously difficult to predict with good accuracy?

We provide a spectrum of new theoretical insights and practical results for finding a Minimum Dilation Triangulation (MDT), a natural geometric optimization problem of considerable previous attention: Given a set P of n points in the plane, find a triangulation T, such that a shortest Euclidean path in T between any pair of points increases by the smallest possible factor compared to their straight-line distance. No polynomial-time algorithm is known for the problem; moreover, evaluating the objective function involves computing the sum of (possibly many) square roots. On the other hand, the problem is not known to be NP-hard. (1) We provide practically robust methods and implementations for computing an MDT for benchmark sets with up to 30,000 points in reasonable time on commodity hardware, based on new geometric insights into the structure of optimal edge sets. Previous methods only achieved results for up to 200 points, so we extend the range of optimally solvable instances by a factor of 150. (2) We develop scalable techniques for accurately evaluating many shortest-path queries that arise as large-scale sums of square roots, allowing us to certify exact optimal solutions, with previous work relying on (possibly inaccurate) floating-point computations. (3) We resolve an open problem by establishing a lower bound of 1.44116 on the dilation of the regular 84-gon (and thus for arbitrary point sets), improving the previous worst-case lower bound of 1.4308 and greatly reducing the remaining gap to the upper bound of 1.4482 from the literature. In the process, we provide optimal solutions for regular n-gons up to n = 100.

We consider algorithmic problems motivated by modular robotic reconfiguration in the sliding square model, in which we are given n square-shaped modules in a (labeled or unlabeled) start configuration and need to find a schedule of sliding moves to transform it into a desired goal configuration, maintaining connectivity of the configuration at all times. Recent work has aimed at minimizing the total number of moves, resulting in fully sequential schedules that can perform reconfiguration in 𝒪(n²) moves, or 𝒪(nP) for arrangements of bounding box perimeter size P. We provide first results in the sliding square model that exploit parallel motion, performing reconfiguration in worst-case optimal makespan of 𝒪(P). We also provide tight bounds on the complexity of the problem by showing that even deciding the possibility of reconfiguration within makespan 1 is NP-complete in the unlabeled case. In the labeled variant, we note that deciding the same for makespan 2 is NP-complete, while makespan 1 is straightforward.

Tilt models offer intuitive and clean definitions of complex systems in which particles are influenced by global control commands. Despite a wide range of applications, there has been almost no theoretical investigation into the associated issues of filling and draining geometric environments. This is partly because a globally controlled system (i.e., passive matter) exhibits highly complex behavior that cannot be locally restricted. Thus, there is a strong need for theoretical studies that investigate these models both (1) in terms of relative power to each other, and (2) from a complexity theory perspective. In this work, we provide (1) general tools for comparing and contrasting different models of global control, and (2) both complexity and algorithmic results on filling and draining.

A common robotics sensing problem is to place sensors to robustly monitor a set of assets, where robustness is assured by requiring asset$p$to be monitored by at least$\kappa(p)$sen-sors. Given$n$assets that must be observed by$m$sensors, each with a disk-shaped sensing region, where should the sensors be placed to minimize the total area observed? We provide and analyze a fast heuristic for this problem. We then use the heuristic to initialize an exact Integer Program-ming solution. Subsequently, we enforce separation constraints between the sensors by modifying the integer program formulation and by changing the disk candidate set.

We investigate the Dispersive Art Gallery Problem with vertex guards and rectangular visibility (r-visibility) for a class of orthogonal polygons that reflect the properties of real-world floor plans: these office-like polygons consist of rectangular rooms and corridors. In the dispersive variant of the Art Gallery Problem, the objective is not to minimize the number of guards but to maximize the minimum geodesic L₁-distance between any two guards, called the dispersion distance. Our main contributions are as follows. We prove that determining whether a vertex guard set can achieve a dispersion distance of 4 in office-like polygons is NP-complete, where vertices of the polygon are restricted to integer coordinates. Additionally, we present a simple worst-case optimal algorithm that guarantees a dispersion distance of 3 in polynomial time. Our complexity result extends to polyominoes, resolving an open question posed by Rieck and Scheffer [Christian Rieck and Christian Scheffer, 2024]. When vertex coordinates are allowed to be rational, we establish analogous results, proving that achieving a dispersion distance of 2+ε is NP-hard for any ε > 0, while the classic Art Gallery Problem remains solvable in polynomial time for this class of polygons. Furthermore, we give a straightforward polynomial-time algorithm that computes worst-case optimal solutions with a dispersion distance 2. On the other hand, for the more restricted class of hole-free independent office-like polygons, we propose a dynamic programming approach that computes optimal solutions. Moreover, we demonstrate that the problem is practically tractable for arbitrary orthogonal polygons. To this end, we compare solvers based on SAT, CP, and MIP formulations. Notably, SAT solvers efficiently compute optimal solutions for randomly generated instances with up to 1600 vertices in under 15s.

Modern software systems are typically configurable, a fundamental prerequisite for wide applicability and reusability. This flexibility poses an extraordinary challenge for quality assurance, as the enormous number of possible configurations makes it impractical to test each of them separately. This is where t-wise interaction sampling can be used to systematically cover the configuration space and detect unknown feature interactions. Over the last two decades, numerous algorithms for computing small interaction samples have been studied, providing improvements for a range of heuristic results; nevertheless, it has remained unclear how much these results can still be improved. We present a significant breakthrough: a fundamental framework, based on the mathematical principle of duality , for combining near-optimal solutions with provable lower bounds on the required sample size. This implies that we no longer need to work on heuristics with marginal or no improvement, but can certify the solution quality by establishing a limit on the remaining gap; in many cases, we can even prove optimality of achieved solutions. This theoretical contribution also provides extensive practical improvements: Our algorithm SampLNS was tested on 47 small- and medium-sized configurable systems from the existing literature. SampLNS can reliably find samples of smaller size than previous methods in \(85\%\) of the cases; moreover, we can achieve and prove optimality of solutions for \(63\%\) of all instances. This makes it possible to avoid cumbersome efforts of minimizing samples by researchers as well as practitioners, and substantially save testing resources for most configurable systems.

We present progress on the problem of reconfiguring a 2D arrangement of building material by a cooperative group of robots. These robots must avoid collisions, deadlocks, and are subjected to the constraint of maintaining connectivity of the structure. We develop two reconfiguration methods, one based on spatio-temporal planning, and one based on target swapping, to increase building efficiency. The first method can significantly reduce planning times compared to other multi-robot planners. The second method helps to reduce the amount of time robots spend waiting for paths to be cleared, and the overall distance traveled by the robots.

Abstract When considering motion planning for a swarm of n labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, collision-free moves. The objective is to reach the new configuration in a minimum amount of time. Problems of this type have been considered before, with recent notable results achieving constant stretch for parallel reconfiguration: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, the total duration of an overall schedule can be bounded to $$\mathcal {O}(d)$$ O ( d ) , which is optimal up to constant factors. An important constraint for coordinated reconfiguration is to keep the swarm connected after each time step. In previous work, constant stretch could only be achieved if disconnected reconfiguration is allowed, or for scaled configurations of unlabeled robots; on the other hand, the existence of non-constant lower bounds on the stretch factor was unknown. We resolve these major open problems by (1) establishing a lower bound of $$\Omega (\sqrt{n})$$ Ω ( n ) for connected, labeled reconfiguration and, most importantly, by (2) proving that for scaled arrangements, constant stretch for connected, labeled reconfiguration can be achieved. In addition, we show that (3) it is -complete to decide whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a schedule of makespan 1 exists.

Abstract We provide the solution for a fundamental problem of geometric optimization by giving a complete characterization of worst-case optimal disk coverings of rectangles: For any $$\lambda \ge 1$$ λ ≥ 1 , the critical covering area $$A^*(\lambda )$$ A ∗ ( λ ) is the minimum value for which any set of disks with total area at least $$A^*(\lambda )$$ A ∗ ( λ ) can cover a rectangle of dimensions $$\lambda \times 1$$ λ × 1 . We show that there is a threshold value $$\lambda _2 = \sqrt{\sqrt{7}/2 - 1/4} \approx 1.035797\ldots $$ λ 2 = 7 / 2 - 1 / 4 ≈ 1.035797 … , such that for $$\lambda <\lambda _2$$ λ < λ 2 the critical covering area $$A^*(\lambda )$$ A ∗ ( λ ) is $$A^*(\lambda )=3\pi \left( \frac{\lambda ^2}{16} +\frac{5}{32} + \frac{9}{256\lambda ^2}\right) $$ A ∗ ( λ ) = 3 π λ 2 16 + 5 32 + 9 256 λ 2 , and for $$\lambda \ge \lambda _2$$ λ ≥ λ 2 , the critical area is $$A^*(\lambda )=\pi (\lambda ^2+2)/4$$ A ∗ ( λ ) = π ( λ 2 + 2 ) / 4 ; these values are tight. For the special case $$\lambda =1$$ λ = 1 , i.e., for covering a unit square, the critical covering area is $$\frac{195\pi }{256}\approx 2.39301\ldots $$ 195 π 256 ≈ 2.39301 … . The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.

Abstract We investigate several geometric problems of finding tours and cycle covers with minimum turn cost, which have been studied in the past, with complexity, approximation results, and open problems dating back to work by Arkin et al. in 2001. Many new practical applications have spawned variants: For full coverage, all points have to be covered, for subset coverage, specific points have to be covered, and for penalty coverage, points may be left uncovered by incurring a penalty. We show that finding a minimum-turn (full) cycle cover is NP-hard even in 2-dimensional grid graphs, solving the long-standing open Problem 53 in The Open Problems Project edited by Demaine, Mitchell and O’Rourke. We also prove NP-hardness of finding a subset cycle cover of minimum turn cost in thin grid graphs, for which Arkin et al. gave a polynomial-time algorithm for full coverage; this shows that their boundary techniques cannot be applied to compute exact solutions for subset and penalty variants. We also provide a number of positive results. In particular, we establish the first constant-factor approximation algorithms for all considered subset and penalty problem variants for grid-based instances, based on LP/IP techniques. These geometric versions allow many possible edge directions (and thus, turn angles, such as in hexagonal grids or higher-dimensional variants); our approximation factors improve the combinatorial ones of Arkin et al.

For a given polygonal region P, the Lawn Mowing Problem (LMP) asks for a shortest tour T that gets within Euclidean distance 1 of every point in P; this is equivalent to computing a shortest tour for a unit-disk cutter C that covers all of P. As a geometric optimization problem of natural practical and theoretical importance, the LMP generalizes and combines several notoriously difficult problems, including minimum covering by disks, the Traveling Salesman Problem with neighborhoods (TSPN), and the ∃ℝ-complete Art Gallery Problem (AGP). So far, there have only been theoretical approximation algorithms with worst-case bounds of , where αTSP is the approximation factor for the geometric TSP. Here, αTSP = 1+ ε is theoretically possible by using one of the famous geometric approximation schemes; however, these methods are not practically applicable for concrete instances. Moreover, there have not been any exact methods for the LMP that compute provably near-optimal solutions for instances of interesting size, owing to the combination of geometric difficulties, such as a succinct characterization of optimal solutions, as well as the lack of useful lower bounds that provide practically small performance gaps. In this paper, we conduct the first study of the Lawn Mowing Problem with a focus on practical computation of near-optimal solutions. To this end, we provide new theoretical insights: Optimal solutions are polygonal paths with a bounded number of vertices, i.e., they do not have any curved pieces, allowing a restriction to straight-line solutions; on the other hand, there can be relatively simple instances for which optimal solutions require a large class of irrational coordinates. On the practical side, we present a primal-dual approach with provable convergence properties based on solving a special case of the TSPN restricted to witness sets. In each iteration, this establishes both a valid solution and a valid lower bound, and thereby a bound on the remaining optimality gap. As we demonstrate in an extensive computational study, this allows us to achieve provably optimal and near-optimal solutions for a large spectrum of benchmark instances with up to 2000 vertices. * The full version of the paper can be accessed at https://arxiv.org/abs/2211.05891. This work was supported by DFG project Computational Geometry: Solving Hard Optimization Problems (CG:SHOP), FE407/21-1.

For a given polygonal region P, the Lawn Mowing Problem (LMP) asks for a shortest tour T that gets within Euclidean distance 1/2 of every point in P; this is equivalent to computing a shortest tour for a unit-diameter cutter C that covers all of P. As a generalization of the Traveling Salesman Problem, the LMP is NP-hard; unlike the discrete TSP, however, the LMP has defied efforts to achieve exact solutions, due to its combination of combinatorial complexity with continuous geometry. We provide a number of new contributions that provide insights into the involved difficulties, as well as positive results that enable both theoretical and practical progress. (1) We show that the LMP is algebraically hard: it is not solvable by radicals over the field of rationals, even for the simple case in which P is a 2×2 square. This implies that it is impossible to compute exact optimal solutions under models of computation that rely on elementary arithmetic operations and the extraction of kth roots, and explains the perceived practical difficulty. (2) We exploit this algebraic analysis for the natural class of polygons with axis-parallel edges and integer vertices (i.e., polyominoes), highlighting the relevance of turn-cost minimization for Lawn Mowing tours, and leading to a general construction method for feasible tours. (3) We show that this construction method achieves theoretical worst-case guarantees that improve previous approximation factors for polyominoes. (4) We demonstrate the practical usefulness beyond polyominoes by performing an extensive practical study on a spectrum of more general benchmark polygons: We obtain solutions that are better than the previous best values by Fekete et al., for instance sizes up to 20 times larger.

Abstract We consider the problem of connected coordinated motion planning for a large collective of simple, identical robots: From a given start grid configuration of robots, we need to reach a desired target configuration via a sequence of parallel, collision-free robot motions, such that the set of robots induces a connected grid graph at all integer times. The objective is to minimize the makespan of the motion schedule, i.e., to reach the new configuration in a minimum amount of time. We show that this problem is -complete, even for deciding whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved. On the algorithmic side, we establish simultaneous constant-factor approximation for two fundamental parameters, by achieving constant stretch for constant scale. Scaled shapes (which arise by increasing all dimensions of a given object by the same multiplicative factor) have been considered in previous seminal work on self-assembly, often with unbounded or logarithmic scale factors; we provide methods for a generalized scale factor, bounded by a constant. Moreover, our algorithm achieves a constant stretch factor: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, then the total duration of our overall schedule is $$\mathcal {O}(d)$$ O ( d ) , which is optimal up to constant factors.

Abstract We provide a tight result for a fundamental problem arising from packing disks into a circular container: The critical density of packing disks in a disk is 0.5. This implies that any set of (not necessarily equal) disks of total area $$\delta \le 1/2$$ δ ≤ 1 / 2 can always be packed into a disk of area 1; on the other hand, for any $$\varepsilon >0$$ ε > 0 there are sets of disks of area $$1/2+\varepsilon $$ 1 / 2 + ε that cannot be packed. The proof uses a careful manual analysis, complemented by a minor automatic part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms.

For biomedical applications in targeted therapy delivery and interventions, a large swarm of micro-scale particles (“agents”) has to be moved through a maze-like environment (“vascular system”) to a target region (“tumor”). Due to limited on-board capabilities, these agents cannot move autonomously; instead, they are controlled by an external global force that acts uniformly on all particles. In this work, we demonstrate how to use a time-varying magnetic field to gather particles to a desired location. We use reinforcement learning to train networks to efficiently gather particles. Methods to overcome the simulation-to-reality gap are explained, and the trained networks are deployed on a set of mazes and goal locations. The hardware experiments demonstrate fast convergence, and robustness to both sensor and actuation noise. To encourage extensions and to serve as a benchmark for the reinforcement learning community, the code is available at Github.

When considering motion planning for a swarm of $n$ labeled robots, we need to rearrange a given start configuration into a desired target configuration via a sequence of parallel, collision-free robot motions. The objective is to reach the new configuration in a minimum amount of time; an important constraint is to keep the swarm connected at all times. Problems of this type have been considered before, with recent notable results achieving constant stretch for not necessarily connected reconfiguration: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of $d$, the total duration of an overall schedule can be bounded to $\mathcal{O}(d)$, which is optimal up to constant factors. However, constant stretch could only be achieved if disconnected reconfiguration is allowed, or for scaled configurations (which arise by increasing all dimensions of a given object by the same multiplicative factor) of unlabeled robots. We resolve these major open problems by (1) establishing a lower bound of $Ω(\sqrt{n})$ for connected, labeled reconfiguration and, most importantly, by (2) proving that for scaled arrangements, constant stretch for connected reconfiguration can be achieved. In addition, we show that (3) it is NP-complete to decide whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved.

Abstract We provide algorithmic methods for connected reconfiguration of lattice-based cellular structures by finite-state robots, motivated by large-scale constructions in space. We present algorithms that are able to detect and reconfigure arbitrary polyominoes, while also preserving connectivity of a structure during reconfiguration; we also provide mathematical proofs and performance guarantees. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.

MOTIVATION: Disease module mining methods (DMMMs) extract subgraphs that constitute candidate disease mechanisms from molecular interaction networks such as protein-protein interaction (PPI) networks. Irrespective of the employed models, DMMMs typically include non-robust steps in their workflows, i.e. the computed subnetworks vary when running the DMMMs multiple times on equivalent input. This lack of robustness has a negative effect on the trustworthiness of the obtained subnetworks and is hence detrimental for the widespread adoption of DMMMs in the biomedical sciences. RESULTS: To overcome this problem, we present a new DMMM called ROBUST (robust disease module mining via enumeration of diverse prize-collecting Steiner trees). In a large-scale empirical evaluation, we show that ROBUST outperforms competing methods in terms of robustness, scalability and, in most settings, functional relevance of the produced modules, measured via KEGG (Kyoto Encyclopedia of Genes and Genomes) gene set enrichment scores and overlap with DisGeNET disease genes. AVAILABILITY AND IMPLEMENTATION: A Python 3 implementation and scripts to reproduce the results reported in this article are available on GitHub: https://github.com/bionetslab/robust, https://github.com/bionetslab/robust-eval. SUPPLEMENTARY INFORMATION: Supplementary data are available at Bioinformatics online.

We illustrate and animate the classic problem of deciding whether a given graph has an Eulerian path. Starting with a collection of instances of increasing difficulty, we present a set of pictorial instructions, and show how they can be used to solve all instances. These IDEA instructions ("A series of nonverbal algorithm assembly instructions") have proven to be both entertaining for experts and enlightening for novices. We (w)rap up with a song and dance to Euler’s original instance.

We provide a tight result for a fundamental problem arising from packing squares into a circular container: The critical density of packing squares into a disk is $δ=\frac{8}{5π}\approx 0.509$. This implies that any set of (not necessarily equal) squares of total area $A \leq \frac{8}{5}$ can always be packed into a disk with radius 1; in contrast, for any $\varepsilon>0$ there are sets of squares of total area $\frac{8}{5}+\varepsilon$ that cannot be packed, even if squares may be rotated. This settles the last (and arguably, most elusive) case of packing circular or square objects into a circular or square container: The critical densities for squares in a square $\left(\frac{1}{2}\right)$, circles in a square $\left(\fracπ{(3+2\sqrt{2})}\approx 0.539\right)$ and circles in a circle $\left(\frac{1}{2}\right)$ have already been established, making use of recursive subdivisions of a square container into pieces bounded by straight lines, or the ability to use recursive arguments based on similarity of objects and container; neither of these approaches can be applied when packing squares into a circular container. Our proof uses a careful manual analysis, complemented by a computer-assisted part that is based on interval arithmetic. Beyond the basic mathematical importance, our result is also useful as a blackbox lemma for the analysis of recursive packing algorithms. At the same time, our approach showcases the power of a general framework for computer-assisted proofs, based on interval arithmetic.

We consider the problem of coordinated motion planning for a swarm of simple, identical robots: From a given start grid configuration of robots, we need to reach a desired target configuration via a sequence of parallel, continuous, collision-free robot motions, such that the set of robots induces a connected grid graph at all integer times. The objective is to minimize the makespan of the motion schedule, i.e., to reach the new configuration in a minimum amount of time. We show that this problem is NP-hard, even for deciding whether a makespan of 2 can be achieved, while it is possible to check in polynomial time whether a makespan of 1 can be achieved. On the algorithmic side, we establish simultaneous constant-factor approximation for two fundamental parameters, by achieving constant stretch for constant scale. Scaled shapes (which arise by increasing all dimensions of a given object by the same multiplicative factor) have been considered in previous seminal work on self-assembly, often with unbounded or logarithmic scale factors; we provide methods for a generalized scale factor, bounded by a constant. Moreover, our algorithm achieves a constant stretch factor: If mapping the start configuration to the target configuration requires a maximum Manhattan distance of d, then the total duration of our overall schedule is 𝒪(d), which is optimal up to constant factors.

We consider a spectrum of geometric optimization problems motivated by contexts such as satellite communication and astrophysics. In the problem Minimum Scan Cover with Angular Costs, we are given a graph G that is embedded in Euclidean space. The edges of G need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex incurs some cost in terms of energy or rotation time that is proportional to the corresponding rotation angle. Our goal is to compute schedules that minimize the following objective functions: (i) in Minimum Makespan Scan Cover (MSC-MS), this is the time until all edges are scanned; (ii) in Minimum Total Energy Scan Cover (MSC-TE), the sum of all rotation angles; (iii) in Minimum Bottleneck Energy Scan Cover (MSC-BE), the maximum total rotation angle at one vertex. Previous theoretical work on MSC-MS revealed a close connection to graph coloring and the cut cover problem, leading to hardness and approximability results. In this paper, we present polynomial-time algorithms for 1D instances of MSC-TE and MSC-BE, but NP-hardness proofs for bipartite 2D instances. For bipartite graphs in 2D, we also give 2-approximation algorithms for both MSC-TE and MSC-BE. Most importantly, we provide a comprehensive study of practical methods for all three problems. We compare three different mixed-integer programming and two constraint programming approaches, and show how to compute provably optimal solutions for geometric instances with up to 300 edges. Additionally, we compare the performance of different meta-heuristics for even larger instances.

We provide a comprehensive study of a natural graph optimization problem that arises from transition costs between incident edges. In the problem Minimum Scan Cover with Angular Costs (MSC), we are given a graph $G$ that is embedded in Euclidean space. The edges of $G$ need to be scanned, i.e., probed from both of their vertices. In order to scan their edge, two vertices need to face each other; changing the heading of a vertex takes some time proportional to the corresponding turn angle. Our goal is to minimize the time until all scans are completed, i.e., to compute a schedule of minimum makespan. A real-world motivation arises in the context of satellite communication and astrophysics. We show that MSC is closely related to both graph coloring and the minimum (directed and undirected) cut cover problem; in particular, we show that the minimum scan time for instances in 1D and 2D lies in $\Theta(\log \chi (G))$, while for 3D the minimum scan time is not upper bounded by $\chi (G)$. We use this relationship to prove that the existence of a constant-factor approximation implies P $=$ NP, even for one-dimensional instances. In 2D, we show that it is NP-hard to approximate a minimum scan cover within less than a factor of $\nicefrac{3}{2}$, even for bipartite graphs; conversely, we present a 9/2-approximation algorithm for this scenario. Generally, we give an $O(c)$-approximation for $k$-colored graphs with $k\leq \chi(G)^{c}$. For general metric cost functions, we provide approximation algorithms whose performance guarantees depend on the arboricity of the graph.

In this video, we consider recognition and reconfiguration of lattice-based cellular structures by very simple robots with only basic functionality. The underlying motivation is the construction and modification of space facilities of enormous dimensions, where the combination of new materials with extremely simple robots promises structures of previously unthinkable size and flexibility. We present algorithmic methods that are able to detect and reconfigure arbitrary polyominoes, based on finite-state robots, while also preserving connectivity of a structure during reconfiguration. Specific results include methods for determining a bounding box, scaling a given arrangement, and adapting more general algorithms for transforming polyominoes.

In this video, we present theoretical and practical methods for achieving arbitrary reconfiguration of a set of objects, based on the use of external forces, such as a magnetic field or gravity: Upon actuation, each object is pushed in the same direction. This concept can be used for a wide range of applications in which particles do not have their own energy supply or in which they are subject to the same global control commands. A crucial challenge for achieving any desired target configuration is breaking global symmetry in a controlled fashion. Previous work (some of which was presented during SoCG 2015) made use of specifically placed barriers; however, introducing precisely located obstacles into the workspace is impractical for many scenarios. In this paper, we present a different, less intrusive method: making use of the interplay between static friction with a boundary and the external force to achieve arbitrary reconfiguration. Our key contributions are theoretical characterizations of the critical coefficient of friction that is sufficient for rearranging two particles in triangles, convex polygons, and regular polygons; a method for reconfiguring multiple particles in rectangular workspaces, and deriving practical algorithms for these rearrangements. Hardware experiments show the efficacy of these procedures, demonstrating the usefulness of this novel approach.

In this video we describe why producing a Computational Geometry video is a good idea, what it takes to make one, and how to actually do it. This includes a guide for the overall process, a number of examples, and a variety of tips and tricks.

We provide the solution for a fundamental problem of geometric optimization by giving a complete characterization of worst-case optimal disk coverings of rectangles: For any $λ\geq 1$, the critical covering area $A^*(λ)$ is the minimum value for which any set of disks with total area at least $A^*(λ)$ can cover a rectangle of dimensions $λ\times 1$. We show that there is a threshold value $λ_2 = \sqrt{\sqrt{7}/2 - 1/4} \approx 1.035797\ldots$, such that for $λ

In this video, we motivate and visualize a fundamental result for covering a rectangle by a set of non-uniform circles: For any λ ≥ 1, the critical covering area A^*(λ) is the minimum value for which any set of disks with total area at least A^*(λ) can cover a rectangle of dimensions λ× 1. We show that there is a threshold value λ₂ = √(√7/2 - 1/4) ≈ 1.035797…, such that for λ < λ₂ the critical covering area A^*(λ) is A^*(λ) = 3π(λ²/16 + 5/32 + 9/256λ²), and for λ ≥ λ₂, the critical area is A^*(λ) = π(λ²+2)/4; these values are tight. For the special case λ=1, i.e., for covering a unit square, the critical covering area is 195π/256 ≈ 2.39301…. We describe the structure of the proof, and show animations of some of the main components.

We investigate algorithmic approaches for targeted drug delivery in a complex, maze-like environment, such as a vascular system. The basic scenario is given by a large swarm of micro-scale particles ("agents") and a particular target region ("tumor") within a system of passageways. Agents are too small to contain on-board power or computation and are instead controlled by a global external force that acts uniformly on all particles, such as an applied fluidic flow or electromagnetic field. The challenge is to deliver all agents to the target region with a minimum number of actuation steps. We provide a number of results for this challenge. We show that the underlying problem is NP-hard, which explains why previous work did not provide provably efficient algorithms. We also develop a number of algorithmic approaches that greatly improve the worst-case guarantees for the number of required actuation steps. We evaluate our algorithmic approaches by a number of simulations, both for deterministic algorithms and searches supported by deep learning, which show that the performance is practically promising.

We consider recognition and reconfiguration of lattice-based cellular structures by very simple robots with only basic functionality. The underlying motivation is the construction and modification of space facilities of enormous dimensions, where the combination of new materials with extremely simple robots promises structures of previously unthinkable size and flexibility; this is also closely related to the newly emerging field of programmable matter. Aiming for large-scale scalability, both in terms of the number of the cellular components of a structure, as well as the number of robots that are being deployed for construction requires simple yet robust robots and mechanisms, while also dealing with various basic constraints, such as connectivity of a structure during reconfiguration. To this end, we propose an approach that combines ultra-light, cellular building materials with extremely simple robots. We develop basic algorithmic methods that are able to detect and reconfigure arbitrary cellular structures, based on robots that have only constant-sized memory. As a proof of concept, we demonstrate the feasibility of this approach for specific cellular materials and robots that have been developed at NASA.

We study a trajectory analysis problem we call the Trajectory Capture Problem (TCP), in which, for a given input set T of trajectories in the plane, and an integer k≥ 2, we seek to compute a set of k points ("portals") to maximize the total weight of all subtrajectories of T between pairs of portals. This problem naturally arises in trajectory analysis and summarization. We show that the TCP is NP-hard (even in very special cases) and give some first approximation results. Our main focus is on attacking the TCP with practical algorithm-engineering approaches, including integer linear programming (to solve instances to provable optimality) and local search methods. We study the integrality gap arising from such approaches. We analyze our methods on different classes of data, including benchmark instances that we generate. Our goal is to understand the best performing heuristics, based on both solution time and solution quality. We demonstrate that we are able to compute provably optimal solutions for real-world instances.

We present algorithmic results for the parallel assembly of many micro-scale objects in two and three dimensions from tiny particles, which has been proposed in the context of programmable matter and self-assembly for building high-yield micro-factories. The underlying model has particles moving under the influence of uniform external forces until they hit an obstacle. Particles bond when forced together with another appropriate particle. Due to the physical and geometric constraints, not all shapes can be built in this manner; this gives rise to the Tilt Assembly Problem (TAP) of deciding constructibility. For simply-connected polyominoes P in 2D consisting of N unit-squares (“tiles”), we prove that TAP can be decided in \(O(N\log N)\) time. For the optimization variant MaxTAP (in which the objective is to construct a subshape of maximum possible size), we show polyAPX -hardness: unless P = NP , MaxTAP cannot be approximated within a factor of \(\Omega (N^{\frac{1}{3}})\) ; for tree-shaped structures, we give an \(\Omega (N^{\frac{1}{2}})\) -approximation algorithm. For the efficiency of the assembly process itself, we show that any constructible shape allows pipelined assembly, which produces copies of P in O (1) amortized time, i.e., N copies of P in O ( N ) time steps. These considerations can be extended to three-dimensional objects: For the class of polycubes P we prove that it is NP -hard to decide whether it is possible to construct a path between two points of P ; it is also NP -hard to decide constructibility of a polycube P . Moreover, it is expAPX -hard to maximize a sequentially constructible path from a given start point.

We study the problem of computing provably optimal and near-optimal solutions for the NP-hard problem of finding covering tours and cycle covers with turn cost, which are of practical importance for a variety of applications, such as pest control and precision farming. Previous work has largely focused on theoretical aspects, such as complexity and approximation. We develop a number of algorithm engineering techniques and refinements to make such theoretical insights practically useful, resulting in a comprehensive study for solving a wide spectrum of large instances. We compute provably optimal solutions for instances with more than 1000 pixels, from the largest previous solved instance size of 76 (de Assis and de Souza 2011). Making use of additional algorithm engineering techniques for handling very large instances, we also compute near-optimal solutions for instances with up to 300 000 pixels, for which we give solutions that are typically within a few percent of our computed lower bounds. We also provide an experimental comparison of a practically refined version of our new theoretical approach with the approximation technique of Arkin et al. that dates back to 2001; we show that our new LP/IP-based approximation method closes 70% of the remaining optimality gap to the lower bound.

We motivate and visualize problems and methods for packing a set of objects into a given container, in particular a set of {different-size} circles or squares into a square or circular container. Questions of this type have attracted a considerable amount of attention and are known to be notoriously hard. We focus on a particularly simple criterion for deciding whether a set can be packed: comparing the total area A of all objects to the area C of the container. The critical packing density delta^* is the largest value A/C for which any set of area A can be packed into a container of area C. We describe algorithms that establish the critical density of squares in a square (delta^*=0.5), of circles in a square (delta^*=0.5390 ...), regular octagons in a square (delta^*=0.5685 ...), and circles in a circle (delta^*=0.5).

Abstract We study parallel online algorithms: For some fixed integer k, a collective of k parallel processes that perform online decisions on the same sequence of events forms a k-copy algorithm. For any given time and input sequence, the overall performance is determined by the best of the k individual total results. Problems of this type have been considered for online makespan minimization; they are also related to optimization with advice on future events, i.e., a number of bits available in advance. Parallel online algorithms are also of interest in practical scenarios in which redundancy is used for hedging against undesired outcomes. We develop Predictive Harmonic $$_3$$ 3 (PH3), a relatively simple family of k-copy algorithms for the online Bin Packing Problem, whose joint competitive factor converges to 1.5 for increasing k. In particular, we show that $$k=6$$ k = 6 suffices to guarantee a factor of 1.5714 for PH3, which is better than 1.57829, the performance of the best known 1-copy algorithm Advanced Harmonic, while $$k=11$$ k = 11 suffices to achieve a factor of 1.5406, beating the known lower bound of 1.54278 for a single online algorithm. In the context of online optimization with advice, our approach implies that 4 bits suffice to achieve a factor better than this bound of 1.54278, which is considerably less than the previous bound of 15 bits.

We develop constant-factor approximation algorithms for minimizing the execution time of a coordinated parallel motion plan for a relatively dense swarm of homogeneous robots in the absence of obstacles. In our first model, each robot has a specified start and destination on the square grid, and in each round of coordinated parallel motion, every robot can move to any adjacent position that is either empty or simultaneously being vacated by another robot. In this model, our algorithm achieves constant stretch factor: if every robot starts at distance at most $d$ from its destination, then the total duration of the overall schedule is $O(d)$, which is optimal up to constant factors. Our result holds for distinguished robots (each robot has a specific destination), identical (unlabeled) robots, and most generally, classes of different robot types (where each destination specifies a required type of robot). We also show that finding the optimal coordinated parallel motion plan is NP-hard, justifying approximation algorithms. In our second model, each robot is a unit-radius disk in the plane, and robots can translate continuously in parallel subject to not intersecting, i.e., having disk centers at $L_2$-distance at least $2$. We prove the same result---constant-factor approximation algorithm to minimizing execution time via constant stretch factor---when the pairwise $L_{\infty}$-distance between disk centers is at least $2\sqrt{2}=2.8284\dots$. On the other hand, for $N$ densely packed disks at distance at most $2+\delta$ for a sufficiently small $\delta>0$, we prove that a stretch factor of $\Omega(N^{1/4})$ is sometimes necessary (when densely packed), while a stretch factor of $\mathcal{O}(N^{1/2})$ is always possible.

We motivate, visualize and demonstrate recent work for minimizing the total execution time of a coordinated, parallel motion plan for a swarm of N robots in the absence of obstacles. Under relatively mild assumptions on the separability of robots, the algorithm achieves constant stretch: If all robots want to move at most d units from their respective starting positions, then the total duration of the overall schedule (and hence the distance traveled by each robot) is O(d) steps; this implies constant-factor approximation for the optimization problem. Also mentioned is an NP-hardness result for finding an optimal schedule, even in the case in which robot positions are restricted to a regular grid. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor Omega(N^{1/4}) is required in the worst case; we establish an achievable stretch factor of O(N^{1/2}) even in this case. We also sketch geometric difficulties of computing optimal trajectories, even for just two unit disks.

This paper introduces techniques for mosquito population surveys in the field using electrified screens (bug zappers) mounted to a UAV. Instrumentation on the UAV logs the UAV path and the GPS location, altitude, and time of each mosquito elimination. Hardware experiments with a UAV equipped with an electrified screen provide real-time measurements of (former) mosquito locations and mosquito-free volumes. Planning a trajectory for the UAV that maximizes the number of mosquito kills is related to the Traveling Salesman Problem, the Lawn Mower Problem and, most closely, Milling with Turn Cost. We reduce this problem to considering variants of covering a grid graph with minimum turn cost, corresponding to optimized energy consumption. We describe an exact method based on Integer Programming that is able to compute provably optimal instances with over 1,500 pixels. These solutions are then implemented on the UAV.

This paper studies the general problem of physically sorting polyominoes according to shape using a 2D, rigid, grid-based workspace. The workspace is designed for sensorless operation, using a fixed set of open-loop force-field inputs that move a polyomino from an inlet port to an outlet port that corresponds to the polyomino's shape, and reset the workspace to classify the next polyomino. This paper proves that static workspaces can classify all orthoconvex polyominoes of width w and height h, and provides a motion sequence and required size of workspace as a function of wand h. By allowing moving polyomino cams that assist in the sorting, we can design dynamic works paces that can sort all polyomi-noes that are “completely filled” using a constant number of force-field inputs. Hardware experiments using magnetic and gravity-based actuation demonstrate these static and dynamic sensorless classifiers at the millimeter scale.

Abstract We contribute results for a set of fundamental problems in the context of programmable matter by presenting algorithmic methods for evaluating and manipulating a collective of particles by a finite automaton that can neither store significant amounts of data, nor perform complex computations, and is limited to a handful of possible physical operations. We provide a toolbox for carrying out fundamental tasks on a given arrangement of particles, using the arrangement itself as a storage device, similar to a higher-dimensional Turing machine with geometric properties. Specific results include time- and space-efficient procedures for bounding, counting, copying, reflecting, rotating or scaling a complex given shape.

Recent years have seen impressive advancements in the development of robots on four wheels: autonomous cars. While much of this progress is owed to a combination of breakthroughs in artificial intelligence and improved sensors, dealing with complex, non-ideal scenarios, where errors or failures can turn out to be catastrophic is still largely unsolved; this will require combining "fast", heuristic approaches of machine learning with "slow", more deliberate methods of discrete algorithms and mathematical optimization. However, many of the real challenges go beyond performance guarantees for individual vehicles and aim at the behavior of swarms: How can we control the complex interaction of a distributed swarm of vehicles, such that the overall behavior can measure up to and go beyond the capabilities of humans? Even though many of our engineering colleagues do not fully realize this yet, there is no doubt that this will have to be based to no small part on expertise in distributed algorithms. I will present a multi-level overview of results and challenges, ranging from information exchanges of small groups all the way to game-theoretic mechanisms for large-scale control. Application scenarios do not just arise from road traffic (where short response times, large numbers of vehicles and individual interests give rise to many difficulties), but also from swarms of autonomous space vehicles (where huge distances, times and energies make distributed methods indispensable).

A conflict-free $k$-coloring of a graph assigns one of $k$ different colors to some of the vertices such that, for every vertex $v$, there is a color that is assigned to exactly one vertex among $v$ and $v$'s neighbors. Such colorings have applications in wireless networking, robotics, and geometry and are well studied in graph theory. Here we study the natural problem of the conflict-free chromatic number $\chi_{CF}(G)$ (the smallest $k$ for which conflict-free $k$-colorings exist). We provide results both for closed neighborhoods $N[v]$, for which a vertex $v$ is a member of its neighborhood, and for open neighborhoods $N(v)$, for which vertex $v$ is not a member of its neighborhood. For closed neighborhoods, we prove the conflict-free variant of the famous Hadwiger Conjecture: If an arbitrary graph $G$ does not contain $K_{k+1}$ as a minor, then $\chi_{CF}(G)\leq k$. For planar graphs, we obtain a tight worst-case bound: three colors are sometimes necessary and always sufficient. In addition, we give a complete characterization of the algorithmic/computational complexity of conflict-free coloring. It is NP-complete to decide whether a planar graph has a conflict-free coloring with one color, while for outerplanar graphs, this can be decided in polynomial time. Furthermore, it is NP-complete to decide whether a planar graph has a conflict-free coloring with two colors, while for outerplanar graphs, two colors always suffice. For the bicriteria problem of minimizing the number of colored vertices subject to a given bound $k$ on the number of colors, we give a full algorithmic characterization in terms of complexity and approximation for outerplanar and planar graphs. For open neighborhoods, we show that every planar bipartite graph has a conflict-free coloring with at most four colors; on the other hand, we prove that for $k\in\{1,2,3\}$, it is NP-complete to decide whether a planar bipartite graph has a conflict-free $k$-coloring. Moreover, we establish that any general planar graph has a conflict-free coloring with at most eight colors.

We present results arising from the problem of sweeping a mosquito-infested area with an Un-manned Aerial Vehicle (UAV) equipped with an electrified metal grid. This is related to the Traveling Salesman Problem, the Lawn Mower Problem and, most closely, Milling with TurnCost. Planning a good trajectory can be reduced to considering penalty and budget variants of covering a grid graph with minimum turn cost. On the theoretical side, we show the solution of a problem from The Open Problems Project that had been open for more than 15 years, and hint at approximation algorithms. On the practical side, we describe an exact method based on Integer Programming that is able to compute provably optimal instances with over 500 pixels. These solutions are actually used for practical trajectories, as demonstrated in the video.

We propose an approach to mapping tissue and vascular systems without the use of contrast agents, based on moving and measuring magnetic particles. To this end, we consider a swarm of particles in a 1D or 2D grid that can be tracked and controlled by an external agent. Control inputs are applied uniformly so that each particle experiences the same applied forces. We present algorithms for three tasks: (1) Mapping, i.e., building a representation of the free and obstacle regions of the workspace; (2) Subset Coverage, i.e., ensuring that at least one particle reaches each of a set of desired locations; and (3) Coverage, i.e., ensuring that every free region on the map is visited by at least one particle. These tasks relate to a large body of previous work from robot navigation, both from theory and practice, which is based on individual control. We provide theoretical insights that have potential relevance for fast MRI scans with magnetically controlled contrast media. In particular, we develop a fundamentally new approach for searching for an object at an unknown distance D, where the search is subject to two different and independent cost parameters for moving and for measuring. We show that regardless of the relative cost of these two operations, there is a simple O(log D/log log D)-competitive strategy, which is the best possible. Also, we provide practically useful and computationally efficient strategies for higher-dimensional settings. These algorithms extend to any number of particles and show that additional particles tend to reduce the mean and the standard deviation of the time required for each task.

A conflict-free k-coloring of a graph assigns one of k different colors to some of the vertices such that, for every vertex v, there is a color that is assigned to exactly one vertex among v and v's neighbors. Such colorings have applications in wireless networking, robotics, and geometry, and are well-studied in graph theory. Here we study the natural problem of the conflict-free chromatic number xCF(G) (the smallest k for which conflict-free k-colorings exist), with a focus on planar graphs. For general graphs, we prove the conflict-free variant of the famous Hadwiger Conjecture: If G does not contain Kk+1 as a minor, then xCF(G) < k. For planar graphs, we obtain a tight worst-case bound: three colors are sometimes necessary and always sufficient. In addition, we give a complete characterization of the algorithmic/computational complexity of conflict-free coloring. It is NP-complete to decide whether a planar graph has a conflict-free coloring with one color, while for outer- planar graphs, this can be decided in polynomial time. Furthermore, it is NP-complete to decide whether a planar graph has a conflict-free coloring with two colors, while for outerplanar graphs, two colors always suffice. For the bicriteria problem of minimizing the number of colored vertices subject to a given bound k on the number of colors, we give a full algorithmic characterization in terms of complexity and approximation for outerplanar and planar graphs.

Databases allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in order to minimize the footprint on disk. When previously allocated blocks cannot be moved, this problem is called the memory allocation problem. The competitive ratio for this problem has matching upper and lower bounds that are logarithmic in the number of requests and in the ratio of the largest to smallest requests. This article defines the storage reallocation problem, where previously allocated blocks can be moved, or reallocated , but at some cost. This cost is determined by the allocation/reallocation cost function . The objective is to minimize the storage footprint, that is, the largest memory address containing an allocated object, while simultaneously minimizing the reallocation costs. This article gives asymptotically optimal algorithms for storage reallocation, in which the storage footprint is at most (1+ ϵ) times optimal, and the reallocation cost is O ((1/ϵ)log (1/ϵ)) times the original allocation cost, that is, it is within a constant factor of optimal when ϵ is a constant. The algorithms are cost oblivious , which means they achieve these bounds with no knowledge of the allocation/reallocation cost function, as long as the cost function is subadditive.

We provide a spectrum of results for the Universal Guard Problem, in which one is to obtain a small set of points ("guards") that are "universal" in their ability to guard any of a set of possible polygonal domains in the plane. We give upper and lower bounds on the number of universal guards that are always sufficient to guard all polygons having a given set of n vertices, or to guard all polygons in a given set of k polygons on an n-point vertex set. Our upper bound proofs include algorithms to construct universal guard sets of the respective cardinalities.

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 minimum number of relays so that between every pair of sensors there is a path through sensors and/or relays such that the consecutive vertices of the path are within distance r if both vertices are relays and within distance 1 otherwise. The two-tier version adds the restrictions that the path must go through relays, and not through sensors . We present a 3.11-approximation algorithm for the one-tier version and a polynomial-time approximation scheme (PTAS) for the two-tier version. We also show that the one-tier version admits no PTAS, assuming P ≠ NP.

In 1991, Edelsbrunner and Tan gave an O(n2) algorithm for finding the MinMax Length triangulation of a set of points in the plane, but stated the complexity of finding a MaxMin Edge Length Triangulation (MELT) as a natural open problem. We resolve this long-standing problem by showing that computing a MELT is NP-complete. Moreover, we prove that (unless P=NP), there is no polynomial-time approximation algorithm that can approximate MELT within any polynomial factor. While this may be taken as conclusive evidence from a theoretical point of view that the problem is hopelessly intractable, it still makes sense to consider powerful optimization methods, such as integer programming (IP), in order to obtain provably optimal solutions for intances of non-trivial size. A straightforward IP based on pairwise disjointness of the Θ(n2) segments between the n points has Θ(n4) constraints, making this IP hopelessly intractable from a practical point of view, even for relatively small n. The main algorithm engineering twist of this paper is to demonstrate how the combination of geometric insights with refined methods of combinatorial optimization can still help to put together an exact method capable of computing optimal MELT solutions for planar point sets up to n = 200. Our key idea is to exploit specific geometric properties in combination with more compact IP formulations, such that we are able to drastically reduce the IPs. On the practical side, we combine two of the most powerful software packages for the individual components: CGAL for carrying out the geometric computations, and CPLEX for solving the IPs. In addition, we discuss specific analytic aspects of the speedup for random point sets.

We present fundamental progress on the computational universality of swarms of micro- or nano-scale robots in complex environments, controlled not by individual navigation, but by a uniform global, external force. More specifically, we consider a 2D grid world, in which all obstacles and robots are unit squares, and for each actuation, robots move maximally until they collide with an obstacle or another robot. The objective is to control robot motion within obstacles, design obstacles in order to achieve desired permutation of robots, and establish controlled interaction that is complex enough to allow arbitrary computations. In this video, we illustrate progress on all these challenges: we demonstrate NP-hardness of parallel navigation, we describe how to construct obstacles that allow arbitrary permutations, and we establish the necessary logic gates for performing arbitrary in-system computations.

We present and analyze methods for patrolling and surveillance in an environment with a distributed swarm of robots with limited capabilities. Our approach is based on a distributed triangulation of the work space, in which a set of p stationary sensors provides coverage control; in addition, there are r mobile robots that can move between the sensors. Building on our prior work on structured exploration of unknown spaces with multi-robot systems, we can make use of a triangulation that is constructed in a distributed fashion and guarantees good local navigation properties, even when sensors and robots have very limited capabilities.

We present fundamental progress on the computational universality of swarms of micro- or nano-scale robots in complex environments, controlled not by individual navigation, but by a uniform global, external force. Consider a 2D grid world, in which all obstacles and robots are unit squares, and for each actuation, robots move maximally until they collide with an obstacle or another robot. In previous work, we demonstrated components of particle computation in this world, designing obstacle configurations that implement AND and OR logic gates: by using dual-rail logic, we designed NOT, NOR, NAND, XOR, XNOR logic gates. However, we were unable to design a FAN-OUT gate, which is necessary for simulating the full range of complex interactions that are present in arbitrary digital circuits. In this work we resolve this problem by proving unit-sized robots cannot generate a FAN-OUT gate. On the positive side, we resolve the missing component with the help of 2×1 robots, which can create fan-out gates that produce multiple copies of the inputs. Using these gates we are able to establish the full range of computational universality as presented by complex digital circuits. As an example we connect our logic elements to produce a 3-bit counter. We also demonstrate how to implement a data storage element.

We present a number of powerful local mechanisms for maintaining a dynamic swarm of robots with limited capabilities and information, in the presence of external forces and permanent node failures. We propose a set of local continuous algorithms that together produce a generalization of a Euclidean Steiner tree. At any stage, the resulting overall shape achieves a good compromise between local thickness, global connectivity, and flexibility to further continuous motion of the terminals. The resulting swarm behavior scales well, is robust against node failures, and performs close to the best known approximation bound for a corresponding centralized static optimization problem.

We consider the problem of organizing a scattered group of n robots in two-dimensional space. The communication graph of the swarm is connected, but there is no central authority for organizing it. We want to arrange them into a sorted and equally-spaced array between the robots with lowest and highest label, while maintaining a connected communication network. In this paper, we describe a distributed method to accomplish these goals, without using central control, while also keeping time, travel distance and communication cost at a minimum. We proceed in a number of stages (leader election, initial path construction, subtree contraction, geometric straightening, and distributed sorting), none of which requires a central authority, but still accomplishes best possible parallelization. The overall arraying is performed in O(n) time, O(n2) individual messages, and O(n) travel distance per robot. Implementation of the sorting and navigation use communication messages of fixed size, and are a practical solution for large populations of low-cost robots.

In this paper we explore the power of geometry to overcome the limitations of non-cooperative self-assembly. We define a generalization of the abstract Tile Assembly Model (aTAM), such that a tile system consists of a collection of polyomino tiles, the Polyomino Tile Assembly Model (polyTAM), and investigate the computational powers of polyTAM systems at temperature 1, where attachment among tiles occurs without glue cooperation (i.e., without the enforcement that more than one tile already existing in an assembly must contribute to the binding of a new tile). Systems composed of the unit-square tiles of the aTAM at temperature 1 are believed to be incapable of Turing universal computation (while cooperative systems, with temperature > 1, are able). As our main result, we prove that for any polyomino P of size 3 or greater, there exists a temperature-1 polyTAM system containing only shape-P tiles that is computationally universal. Our proof leverages the geometric properties of these larger (relative to the aTAM) tiles and their abilities to effectively utilize geometric blocking of particular growth paths of assemblies, while allowing others to complete. In order to prove the computational powers of polyTAM systems, we also prove a number of geometric properties held by all polyominoes of size ≥ 3. To round out our main result, we provide strong evidence that size-1 (i.e. aTAM tiles) and size-2 polyomino systems are unlikely to be computationally universal by showing that such systems are incapable of geometric bitreading, which is a technique common to all currently known temperature-1 computationally universal systems. We further show that larger polyominoes with a limited number of binding positions are unlikely to be computationally universal, as they are only as powerful as temperature-1 aTAM systems. Finally, we connect our work with other work on domino self-assembly to show that temperature-1 assembly with at least 2 distinct shapes, regardless of the shapes or their sizes, allows for universal computation.

In a reallocating-scheduler problem, jobs may be inserted and deleted from the system over time. Unlike in traditional online scheduling problems, where a job's placement is immutable, in reallocation problems the schedule may be adjusted, but at some cost. The goal is to maintain an approximately optimal schedule while also minimizing the reallocation cost for changing the schedule.

Micro- and nanorobots are often controlled by global input signals, such as an electromagnetic or gravitational field. These fields move each robot maximally until it hits a stationary obstacle or another stationary robot. This paper investigates 2D motion-planning complexity for large swarms of simple mobile robots (such as bacteria, sensors, or smart building material). In previous work we proved it is NP-hard to decide whether a given initial configuration can be transformed into a desired target configuration; in this paper we prove a stronger result: the problem of finding an optimal control sequence is PSPACE-complete. On the positive side, we show we can build useful systems by designing obstacles. We present a reconfigurable hardware platform and demonstrate how to form arbitrary permutations and build a compact absolute encoder. We then take the same platform and use dual-rail logic to build a universal logic gate that concurrently evaluates AND, NAND, NOR and OR operations. Using many of these gates and appropriate interconnects we can evaluate any logical expression.

This paper presents a distributed approach for exploring and triangulating an unknown region using a multirobot system. The resulting triangulation is a physical data structure that is a: compact representation of the workspace, contains distributed knowledge of each triangle, builds the dual graph of the triangulation, and supports reads and writes of auxiliary data. Our algorithm builds a triangulation in a closed two-dimensional Euclidean environment, starting from a single location. It provides coverage with a breadth-first search pattern and completeness guarantees. We show that the computational and communication requirements to build and maintain the triangulation and its dual graph are small. We then present a physical navigation algorithm that uses the dual graph, and show that the resulting path lengths are within a constant factor of the shortest-path Euclidean distance. Finally, we validate our theoretical results with experiments on triangulating a region with a system of low-cost robots. Analysis of the resulting triangulation shows that most of the triangles are of high quality, and cover a large area. Implementation of the triangulation, dual graph, and navigation all use communication messages of fixed size, and are a practical solution for large populations of low-cost robots.

Positioning a group of robots at the center of their geodesic Voronoi cells minimizes the worst-case response time for any robot to arrive at an exogenous event in the workspace. We construct these cells in a distributed fashion, building on our prior work on triangulating unknown spaces with multi-robot systems. This produces a physical data structure - a set of triangles formed by the positions of the robots that can be used to perform coverage control. This paper presents: 1) A discrete approximation of the geodesic Voronoi cell using the multi-robot triangulation. We call this a topological Voronoi cell, and show that it can be computed efficiently in a distributed fashion and with theoretical guarantees compared to continuous version. 2) A local motion controller to guide navigating robots to the centroid of their topological Voronoi cell. This controller uses bounded communications with a fixed constant, but can produce local extrema that trap navigating robots away from the optimal position. 3) An enhanced local controller using navigation agents to help guide the navigating robot to the optimal position in its Voronoi cell. It also uses bounded communications, but with a constant that can be tuned to trade communications bandwidth for increased accuracy. 4) Hardware experiments that compute the topological Voronoi cell on a group of 14 robots, simulation results that demonstrate local extrema, and the effectiveness of the virtual navigation agents, and simulation results comparing the performance of the patrolling algorithm using and not using topological Voronoi cells.

Databases allocate and free blocks of storage on disk. Freed blocks introduce holes where no data is stored. Allocation systems attempt to reuse such deallocated regions in order to minimize the footprint on disk. When previously allocated blocks cannot be moved, this problem is called the memory allocation problem. It is known to have a logarithmic overhead in the footprint size. This paper defines the storage reallocation problem, where previously allocated blocks can be moved, or reallocated, but at some cost. This cost is determined by the allocation/reallocation cost function. The algorithms presented here are cost oblivious, in that they work for a broad and reasonable class of cost functions, even when they do not know what the cost function actually is.

No abstract available.

In this video, we illustrate how one of the classical areas of computational geometry has gained in practical relevance, which in turn gives rise to new, fascinating geometric problems. In particular, we demonstrate how the robot platform IRMA3D can produce high-resolution, virtual 3D environments, based on a limited number of laser scans. Computing an optimal set of scans amounts to solving an instance of the Art Gallery Problem (AGP): Place a minimum number of stationary guards in a polygonal region P, such that all points in P are guarded.

In traditional on-line problems, such as scheduling, requests arrive over time, demanding available resources. As each request arrives, some resources may have to be irrevocably committed to servicing that request. In many situations, however, it may be possible or even necessary to reallocate previously allocated resources in order to satisfy a new request. This reallocation has a cost. This paper shows how to service the requests while minimizing the reallocation cost.

We propose a new method for defragmenting the module layout of a reconfigurable device, enabled by a novel approach for dealing with communication needs between relocated modules and with inhomogeneities found in commonly used FPGAs. Our method is based on dynamic relocation of module positions during runtime, with only very little reconfiguration overhead; the objective is to maximize the length of contiguous free space that is available for new modules. We describe a number of algorithmic aspects of good defragmentation, and present an optimization method based on tabu search. Experimental results indicate that we can improve the quality of module layout by roughly 50% over the static layout. Among other benefits, this improvement avoids unnecessary rejections of modules.

The classical Art Gallery Problem asks for the minimum number of guards that achieve visibility coverage of a given polygon. This problem is known to be NP-hard, even for very restricted and discrete special cases. For the case of vertex guards and simple orthogonal polygons, Cuoto et al. have recently developed an exact method that is based on a set cover approach. For the general problem (in which both the set of possible guard positions and the point set to be guarded are uncountable), neither constant-factor approximation algorithms nor exact solution methods are known. We present a primal-dual algorithm based on linear programming that provides lower bounds on the necessary number of guards in every step and—in case of convergence and integrality—ends with an optimal solution. We describe our implementation and give results for an assortment of polygons, including non-orthogonal polygons with holes.

In this work we present a protocol for self-synchronized duty-cycling in wireless sensor networks with energy harvesting capabilities. The protocol is implemented in Wiselib, a library of generic algorithms for sensor networks. Simulations are conducted with the sensor network simulator Shawn. They are based on the specifications of real hardware known as iSense sensor nodes. The experimental results show that the proposed mechanism is able to adapt to changing energy availabilities. Moreover, it is shown that the system is very robust against packet loss.

In recent years, tremendous progress has been made in understanding the dynamics of vehicle traffic flow and traffic congestion by interpreting traffic as a multiparticle system. This helps to explain the onset and persistence of many undesired phenomena, for example, traffic jams. It also reflects the apparent helplessness of drivers in traffic, who feel like passive particles that are pushed around by exterior forces; one of the crucial aspects is the inability to communicate and coordinate with other traffic participants. We present distributed methods for solving these fundamental problems, employing modern wireless, ad-hoc, multi-hop networks. The underlying idea is to use these capabilities as the basis for self-organizing methods for coordinating data collection and processing, recognizing traffic phenomena, and changing their structure by coordinated behavior. The overall objective is a multi-level approach that reaches from protocols for local wireless communication, data dissemination, pattern recognition, over hierarchical structuring and coordinated behavior, all the way to large-scale traffic regulation. In this article, we describe three types of results: (i) self-organizing and distributed methods for maintaining and collecting data (using our concept of Hovering Data Clouds ); (ii) adaptive data dissemination for traffic information systems; (iii) methods for self-recognition of traffic jams. We conclude by describing higher-level aspects of our work.

We study a problem related to computer vision: How can a field of sensors compute higher-level properties of observed objects deterministically in sublinear time, without accessing a central authority? This issue is not only important for real-time processing of images, but lies at the very heart of understanding how a brain may be able to function. In particular, we consider a quadratic field of n "smart pixels" on a video chip that observe a B/W image. Each pixel can exchange low-level information with its immediate neighbors. We show that it is possible to compute the centers of gravity along with a principal component analysis of all connected components of the black grid graph in time O(sqrt(n)), by developing appropriate distributed protocols that are modeled after sweepline methods. Our method is not only interesting from a philosophical and theoretical point of view, it is also useful for actual applications for controling a robot arm that has to seize objects on a moving belt. We describe details of an implementation on an FPGA; the code has also been turned into a hardware design for an application-specific integrated circuit (ASIC).

We present a sensor network that monitors a hallway. It consists of 180 load sensors connected to 30 wireless sensor nodes, where the setup is of extremely low cost and easily transferred to other settings. Our network serves as a testbed for in-network data processing algorithms, for which it is highly suitable due to the many correlated sensors.

We propose a new method for defragmenting the module layout of a reconfigurable device, enabled by a novel approach for dealing with communication needs between relocated modules and with inhomogeneities found in commonly used FPGAs. Our method is based on dynamic relocation of module positions during runtime, with only very little reconfiguration overhead; the objective is to maximize the length of contiguous free space that is available for new modules. We describe a number of algorithmic aspects of good defragmentation, and present an optimization method based on tabu search. Experimental results indicate that we can improve the quality of module layout by roughly 50% over static layout. Among other benefits, this improvement avoids unnecessary rejection of modules.

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, repeated insertion and deletion of modules leads to progressive fragmentation of the available space, making defragmentation an important issue. We address this problem by proposing an online and an offline component for the defragmentation of the available space. We consider defragmenting the module layout on a reconfigurable device. This corresponds to solving a 2D strip packing problem. Problems of this type are NP-hard in the strong sense, and previous algorithmic results are rather limited. Based on a graph-theoretic characterization of feasible packings, we develop a method that can solve 2D defragmentation instances of practical size to optimality. Our approach is validated for a set of benchmark instances. We also discuss a simple strategy for dealing with online scenarios, called ldquoleast-interference fitrdquo (LIF); we give a number of analytic results that allow a comparison of LIF with the best offline solution, and demonstrate that it works well on benchmark instances of moderate size.

Protocols and applications that rely on unicast and multicast communication are well accepted and still gain more and more popularity. However, these communication paradigms are not optimal for a class of wireless applications where communication partners neither establish specific relationships nor need roles like client and server between each other before data exchange. Applications we have in mind deal with up to several thousands of peers as autonomous wireless network nodes. Nodes communicate events like traffic accidents in a local region or information of common interest to a larger group of network nodes. Intermediate nodes forward or rather "gossip" information like in a social communication model, comparable to the news of the big fire of Rome in neronian times travelling through Europe and finally reaching villages in rural areas. The challenge of such a concept is to find efficient local rules, which balance communication with respect to bandwidth usage, latency of data, and data delivery ratio. We introduce the promising application AutoNomos - a decentralized traffic information system - which is well suited for the evaluation of such a data dissemination protocol. Next, we present our new approach calledAutoCastthat is well optimized and self-adaptable towards various dynamic topologies. We compareAutoCastagainst the theoretical optimum and existing data dissemination protocols. Finally, simulations will demonstrate the efficiency of the approach.

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 (tj) and radii (rj) that cover a given set of demand points Y∈R2 at the smallest possible cost. We consider cost functions of the form Εjf(rj), where f(r)=rα is the cost of transmission to radius r. Special cases arise for α=1 (sum of radii) and α=2 (total area); power consumption models in wireless network design often use an exponent α>2. Different scenarios arise according to possible restrictions on the transmission centers tj, which may be constrained to belong to a given discrete set or to lie on a line, etc.We obtain several new results, including (a) exact and approximation algorithms for selecting transmission points tj on a given line in order to cover demand points Y∈R2; (b) approximation algorithms (and an algebraic intractability result) for selecting an optimal line on which to place transmission points to cover Y; (c) a proof of NP-hardness for a discrete set of transmission points in R2 and any fixed α>1; and (d) a polynomial-time approximation scheme for the problem of computing a minimum cost covering tour (MCCT), in which the total cost is a linear combination of the transmission cost for the set of disks and the length of a tour/path that connects the centers of the disks.

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 planar shapes (Jordan regions) that are hinged together sequentially at rotatable joints. Our goal is to characterize the familes of planar shapes that admit locked chains, where some configurations cannot be reached by continuous reconfiguration without self-intersection, and which families of planar shapes guarantee universal foldability, where every chain is guaranteed to have a connected configuration space. Previously, only obtuse triangles were known to admit locked shapes, and only line segments were known to guarantee universal foldability. We show that a surprisingly general family of planar shapes, called slender adornments, guarantees universal foldability: roughly, the inward normal from any point on the shape's boundary should intersect the line segment connecting the two incident hinges. In constrast, we show that isosceles triangles with any desired apex angle <90° admit locked chains, which is precisely the threshold beyond which the inward-normal property no longer holds.

No abstract available.

We discuss the problem of simultaneously scheduling, binding and routing a given data flow graph to a coarse-grain architecture consisting of identical processing elements (PEs) that are connected by a nearest-neighbour mesh-like interconnection network. While there are heuristics trying to solve this problem, we develop the first exact method based on integer linear programming. This allows us to achieve provably optimal solutions for two different objective functions, for small to medium instances. In addition, we describe a heuristic that seems to outperform all other known heuristics

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 to increased signal delays and wastes chip space for the reconfigurable multiple bus. We present integer linear programming (ILP) formulations that address both of these problems; both ILPs can be used stand-alone or as building blocks for more involved mathematical models. We validate our models by demonstrating their usefulness for a set of realistic benchmarks.

Many complex structures in our modern world exist independent of the individual entities they are composed of, giving them an "organic" quality. Important examples include traffic phenomena, e.g., traffic jams; despite of strong efforts over many years, centralized computing has been unable to deal with the resulting problems in a satisfactory manner. With the growing power of sensing devices and wireless communication, participants in traffic are no longer restricted to display passive, particle-like behavior; instead, local data exchange makes it technically feasible to aim for decentralized coordination between cars. One fundamental concept for making use of these possibilities comprises Hovering Data Clouds, which consist of relevant information that is kept by ever-changing carriers; a prototypical scenario arises in a traffic jam, where data is maintained by passing it on to newly arriving cars. In this study, we present algorithmic methods for this concept. This paper is part of project AutoNomos1(www.auto- nomos.de), which aims at traffic control in a decentralized manner.

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 be interpreted as higher‐dimensional generalizations of scheduling problems. Using graph‐theoretic structures to describe feasible solutions, we develop a novel exact branch‐and‐bound algorithm. This extends previous work by Fekete and Schepers; a key tool is a new order‐theoretic characterization of feasible extensions of a partial order to a given complementarity graph that is tailor‐made for use in a branch‐and‐bound environment. The usefulness of our approach is validated by computational results.

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 each module to access its peripheries independent from its location through a programmable crossbar, and distributed SRAMs among slices. This allows an unrestricted relocation of modules on the device. Second, the intermodule structure allows an unlimited communication among running modules.

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 dynamic communication infrastructure as well as routing methodologies capable to handle routing in a NoC with obstacles created by dynamically placed components. We prove the unrestricted reachability of components and pins, the deadlock-freeness and we finally show the feasibility of our approach by means on real life example applications.

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 region ("pocket") in order to minimize a cost that depends mainly on the number of turns. These problems arise naturally in manufacturing applications of computational geometry to automatic tool path generation and automatic inspection systems, as well as arc routing ("postman") problems with turn penalties. We prove the NP-completeness of minimum-turn milling and give efficient approximation algorithms for several natural versions of the problem, including a polynomial-time approximation scheme based on a novel adaptation of the m-guillotine method.

We demonstrate how one of the classical areas of computationalgeometry has reached practical application, which in turngives rise to new, fascinating geometric problems.In particular, we discuss the problem of developing a goodonline strategy for anautonomous mobile robot to locate an object that is hidden behinda corner or door.

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 computational results. Visualization is therefore a key issue to develop and operate these networks. Data emitted by individual sensor nodes is collected by the visualization software and passed to a flexible multi-layer plug-in mechanism that renders the information on a canvas. Developers can easily adapt existing or develop new custom tailored plug-ins for their specific application.

No abstract available.

We consider the traveling salesman problem when the cities are points in ℝ d for some fixed d and distances are computed according to geometric distances, determined by some norm. We show that for any polyhedral norm, the problem of finding a tour of maximum length can be solved in polynomial time. If arithmetic operations are assumed to take unit time, our algorithms run in time O ( n f -2 log n ), where f is the number of facets of the polyhedron determining the polyhedral norm. Thus, for example, we have O ( n 2 log n ) algorithms for the cases of points in the plane under the Rectilinear and Sup norms. This is in contrast to the fact that finding a minimum length tour in each case is NP-hard. Our approach can be extended to the more general case of quasi-norms with a not necessarily symmetric unit ball, where we get a complexity of O ( n 2 f -2 log n ).For the special case of two-dimensional metrics with f = 4 (which includes the Rectilinear and Sup norms), we present a simple algorithm with O ( n ) running time. The algorithm does not use any indirect addressing, so its running time remains valid even in comparison based models in which sorting requires Ω( n log n ) time. The basic mechanism of the algorithm provides some intuition on why polyhedral norms allow fast algorithms.Complementing the results on simplicity for polyhedral norms, we prove that, for the case of Euclidean distances in ℝ d for d ≥ 3, the Maximum TSP is NP-hard. This sheds new light on the well-studied difficulties of Euclidean distances.

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 time. Using a graph-theoretic characterization of feasible packings, we are able to solve the following problems. (a) Find the minimal execution time of the given problem on an FPGA of fixed size, (b) Find the FPGA of minimal size to accomplish the tasks within a fired time limit. Furthermore, our approach is perfectly suited for the treatment of precedence constraints for the sequence of tasks, which are present in virtually all practical instances. Additional mathematical structures are developed that lead to a powerful framework for completing optimal solutions. The usefulness is illustrated by computational results.

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 k-median (Weber) problem" where the goal is to select one or more center points that minimize the average distance to a set of points in a demand region.In such problems, the average is computed as an integral over the relevant region, versus the usual discrete sum of distances.The resulting facility location problems are inherently geometric, requiring analysis techniques of computational geometry.We provide polynomial-time algorithms for various versions of the L1 1-median (Weber) problem.We also consider the multiple-center version of the L1 k-median problem, which we prove is NP-hard for large k.

introductionWe discuss properties and values of maximum matchings and minimum median problems for finite point sets.In Dar&&r.we consider "minimum stars".which are defined by a cent& chosen from the given point ' set, such that the total geometric distance min llStl[ to all the points in the set is minimized.If the center point is not required to be an element of the set (i. e., the center may be a Steiner nointj.we net a "minimum Steiner star". of total length -min I[.!?tS'tll."As a consequence of triangle inequality, the total length max IlMatll of any maximum matching is a lower bound for the length min IIStSt() of a minimum Steiner star, which makes the ratio -1 interesting in the context of optimal communication networks.The ratio also appears as the duality gap in an integer programming formulation of a location problem by Tamir and Mitchell.In this paper, we show that, for an even set of points in the plane and Euclidean distances, the ratio max,,Mat,, min llSt.Stl( ,, ,, cannot exceed 2/& This proves a conjecture of Suri, who gave an example where this bound is achieved.For the case of Euclidean distances in two and three dimensions, we also prove upper and lower bounds for the maximal value of the ratios m and z~,/~~$.We give tight upper bounds for the case where distances are measured according to the Manhattan metric: we show that in three-dimensional space, min ll.StStll max lp4atII 'Parts of this work were done while visiting Queen's University, partially supported by the Deutsche Forschungsgemeinschaft, FE 40713-l.t Parts of this work were done while visiting Universitit zu Kiiln, partially supported by NSERC.Permission to make digital or hard copies ol'all or part of this work for personal or classroom use is granted without fee provided that topics are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citalion on the tirst page.To copy otherwise, Lo

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 are a distance d apart, but they do not know the direction in which they should travel. We also consider a situation in which player 1 knows the initial position of player 2, while player 2 is only given information on the initial distance of player 1. Finally we give some results for the case where one of the players is placed at an initial position chosen equiprobably from a finite set of points.

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 a set Q in a simple polygon with vertex set P. We prove that it is NP-complete to find a minimum weight polygon or a maximum weight polygon for a given vertex set, resulting in a proof of NP-completeness for the corresponding area optimization problems. We show that we can find a polygon of more than half the area AR(conv(P)) of the convex hull conv(P) of P, and demonstrate that it is NP-complete to decide whether there is a simple polygon of at least (3/2 + ε)AR(conv(P)). Finally, we prove that for 1 ≤ k ≤ d, 2 ≤ d, it is NP-hard to minimize the volume of the k-dimensional faces of a d-dimensional simple non-degenerate polyhedron with a given vertex set, answering a generalization of a question stated by O'Rourke in 1980.