DROPS

Found 2 Possible Name Variants:

Fekete, Sándor P.
Fekete, Sándor

Fekete, Sándor P.

Document

DOI: 10.4230/LIPIcs.ESA.2023.45

The Lawn Mowing Problem: From Algebra to Algorithms

Authors: Sándor P. Fekete, Dominik Krupke, Michael Perk, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract

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.

Cite as

Sándor P. Fekete, Dominik Krupke, Michael Perk, Christian Rieck, and Christian Scheffer. The Lawn Mowing Problem: From Algebra to Algorithms. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ESA.2023.45,
  author =	{Fekete, S\'{a}ndor P. and Krupke, Dominik and Perk, Michael and Rieck, Christian and Scheffer, Christian},
  title =	{{The Lawn Mowing Problem: From Algebra to Algorithms}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{45:1--45:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.45},
  URN =		{urn:nbn:de:0030-drops-186985},
  doi =		{10.4230/LIPIcs.ESA.2023.45},
  annote =	{Keywords: Geometric optimization, covering problems, tour problems, lawn mowing, algebraic hardness, approximation algorithms, algorithm engineering}
}

@InProceedings{fekete_et_al:LIPIcs.ESA.2023.45,
  author =	{Fekete, S\'{a}ndor P. and Krupke, Dominik and Perk, Michael and Rieck, Christian and Scheffer, Christian},
  title =	{{The Lawn Mowing Problem: From Algebra to Algorithms}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{45:1--45:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.45},
  URN =		{urn:nbn:de:0030-drops-186985},
  doi =		{10.4230/LIPIcs.ESA.2023.45},
  annote =	{Keywords: Geometric optimization, covering problems, tour problems, lawn mowing, algebraic hardness, approximation algorithms, algorithm engineering}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2022.17

Efficiently Reconfiguring a Connected Swarm of Labeled Robots

Authors: Sándor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, and Arne Schmidt

Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)

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, continuous, 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 𝒪(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 Ω(√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-hard 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.

Cite as

Sándor P. Fekete, Peter Kramer, Christian Rieck, Christian Scheffer, and Arne Schmidt. Efficiently Reconfiguring a Connected Swarm of Labeled Robots. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 17:1-17:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ISAAC.2022.17,
  author =	{Fekete, S\'{a}ndor P. and Kramer, Peter and Rieck, Christian and Scheffer, Christian and Schmidt, Arne},
  title =	{{Efficiently Reconfiguring a Connected Swarm of Labeled Robots}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{17:1--17:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-258-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{248},
  editor =	{Bae, Sang Won and Park, Heejin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.17},
  URN =		{urn:nbn:de:0030-drops-173028},
  doi =		{10.4230/LIPIcs.ISAAC.2022.17},
  annote =	{Keywords: Motion planning, parallel motion, bounded stretch, makespan, connectivity, swarm robotics}
}

Document

Media Exposition

DOI: 10.4230/LIPIcs.SoCG.2022.65

Space Ants: Episode II - Coordinating Connected Catoms (Media Exposition)

Authors: Julien Bourgeois, Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Benoît Piranda, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract

How can a set of identical mobile agents coordinate their motions to transform their arrangement from a given starting to a desired goal configuration? We consider this question in the context of actual physical devices called Catoms, which can perform reconfiguration, but need to maintain connectivity at all times to ensure communication and energy supply. We demonstrate and animate algorithmic results, in particular a proof of hardness, as well as an algorithm that guarantees constant stretch for certain classes of arrangements: 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 in 𝒪(d), which is optimal up to constant factors.

Cite as

Julien Bourgeois, Sándor P. Fekete, Ramin Kosfeld, Peter Kramer, Benoît Piranda, Christian Rieck, and Christian Scheffer. Space Ants: Episode II - Coordinating Connected Catoms (Media Exposition). In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 65:1-65:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{bourgeois_et_al:LIPIcs.SoCG.2022.65,
  author =	{Bourgeois, Julien and Fekete, S\'{a}ndor P. and Kosfeld, Ramin and Kramer, Peter and Piranda, Beno\^{i}t and Rieck, Christian and Scheffer, Christian},
  title =	{{Space Ants: Episode II - Coordinating Connected Catoms}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{65:1--65:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.65},
  URN =		{urn:nbn:de:0030-drops-160732},
  doi =		{10.4230/LIPIcs.SoCG.2022.65},
  annote =	{Keywords: Motion planning, parallel motion, bounded stretch, scaled shape, makespan, connectivity, swarm robotics}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2021.9

Connected Coordinated Motion Planning with Bounded Stretch

Authors: Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract

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.

Cite as

Sándor P. Fekete, Phillip Keldenich, Ramin Kosfeld, Christian Rieck, and Christian Scheffer. Connected Coordinated Motion Planning with Bounded Stretch. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 9:1-9:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ISAAC.2021.9,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip and Kosfeld, Ramin and Rieck, Christian and Scheffer, Christian},
  title =	{{Connected Coordinated Motion Planning with Bounded Stretch}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{9:1--9:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.9},
  URN =		{urn:nbn:de:0030-drops-154423},
  doi =		{10.4230/LIPIcs.ISAAC.2021.9},
  annote =	{Keywords: Motion planning, parallel motion, bounded stretch, scaled shape, makespan, connectivity, swarm robotics}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2021.36

Packing Squares into a Disk with Optimal Worst-Case Density

Authors: Sándor P. Fekete, Vijaykrishna Gurunathan, Kushagra Juneja, Phillip Keldenich, Linda Kleist, and Christian Scheffer

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract

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 δ = 8/(5π)≈ 0.509. This implies that any set of (not necessarily equal) squares of total area A ≤ 8/5 can always be packed into a disk with radius 1; in contrast, for any ε > 0 there are sets of squares of total area 8/5+ε 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 (1/2), circles in a square (π/(3+2√2) ≈ 0.539) and circles in a circle (1/2) 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.

Cite as

Sándor P. Fekete, Vijaykrishna Gurunathan, Kushagra Juneja, Phillip Keldenich, Linda Kleist, and Christian Scheffer. Packing Squares into a Disk with Optimal Worst-Case Density. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2021.36,
  author =	{Fekete, S\'{a}ndor P. and Gurunathan, Vijaykrishna and Juneja, Kushagra and Keldenich, Phillip and Kleist, Linda and Scheffer, Christian},
  title =	{{Packing Squares into a Disk with Optimal Worst-Case Density}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.36},
  URN =		{urn:nbn:de:0030-drops-138356},
  doi =		{10.4230/LIPIcs.SoCG.2021.36},
  annote =	{Keywords: Square packing, packing density, tight worst-case bound, interval arithmetic, approximation}
}

Document

Media Exposition

DOI: 10.4230/LIPIcs.SoCG.2021.62

Can You Walk This? Eulerian Tours and IDEA Instructions (Media Exposition)

Authors: Aaron T. Becker, Sándor P. Fekete, Matthias Konitzny, Sebastian Morr, and Arne Schmidt

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

Abstract

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.

Cite as

Aaron T. Becker, Sándor P. Fekete, Matthias Konitzny, Sebastian Morr, and Arne Schmidt. Can You Walk This? Eulerian Tours and IDEA Instructions (Media Exposition). In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 62:1-62:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2021.62,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P. and Konitzny, Matthias and Morr, Sebastian and Schmidt, Arne},
  title =	{{Can You Walk This? Eulerian Tours and IDEA Instructions}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{62:1--62:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.62},
  URN =		{urn:nbn:de:0030-drops-138616},
  doi =		{10.4230/LIPIcs.SoCG.2021.62},
  annote =	{Keywords: Eulerian tours, algorithms, education, IDEA instructions}
}

Document

DOI: 10.4230/LIPIcs.SEA.2021.4

Minimum Scan Cover and Variants - Theory and Experiments

Authors: Kevin Buchin, Sándor P. Fekete, Alexander Hill, Linda Kleist, Irina Kostitsyna, Dominik Krupke, Roel Lambers, and Martijn Struijs

Published in: LIPIcs, Volume 190, 19th International Symposium on Experimental Algorithms (SEA 2021)

Abstract

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.

Cite as

Kevin Buchin, Sándor P. Fekete, Alexander Hill, Linda Kleist, Irina Kostitsyna, Dominik Krupke, Roel Lambers, and Martijn Struijs. Minimum Scan Cover and Variants - Theory and Experiments. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 4:1-4:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{buchin_et_al:LIPIcs.SEA.2021.4,
  author =	{Buchin, Kevin and Fekete, S\'{a}ndor P. and Hill, Alexander and Kleist, Linda and Kostitsyna, Irina and Krupke, Dominik and Lambers, Roel and Struijs, Martijn},
  title =	{{Minimum Scan Cover and Variants - Theory and Experiments}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.4},
  URN =		{urn:nbn:de:0030-drops-137765},
  doi =		{10.4230/LIPIcs.SEA.2021.4},
  annote =	{Keywords: Graph scanning, angular metric, makespan, energy, bottleneck, complexity, approximation, algorithm engineering, mixed-integer programming, constraint programming}
}

@InProceedings{buchin_et_al:LIPIcs.SEA.2021.4,
  author =	{Buchin, Kevin and Fekete, S\'{a}ndor P. and Hill, Alexander and Kleist, Linda and Kostitsyna, Irina and Krupke, Dominik and Lambers, Roel and Struijs, Martijn},
  title =	{{Minimum Scan Cover and Variants - Theory and Experiments}},
  booktitle =	{19th International Symposium on Experimental Algorithms (SEA 2021)},
  pages =	{4:1--4:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-185-6},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{190},
  editor =	{Coudert, David and Natale, Emanuele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2021.4},
  URN =		{urn:nbn:de:0030-drops-137765},
  doi =		{10.4230/LIPIcs.SEA.2021.4},
  annote =	{Keywords: Graph scanning, angular metric, makespan, energy, bottleneck, complexity, approximation, algorithm engineering, mixed-integer programming, constraint programming}
}

Document

DOI: 10.4230/LIPIcs.SEA.2020.5

Probing a Set of Trajectories to Maximize Captured Information

Authors: Sándor P. Fekete, Alexander Hill, Dominik Krupke, Tyler Mayer, Joseph S. B. Mitchell, Ojas Parekh, and Cynthia A. Phillips

Published in: LIPIcs, Volume 160, 18th International Symposium on Experimental Algorithms (SEA 2020)

Abstract

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.

Cite as

Sándor P. Fekete, Alexander Hill, Dominik Krupke, Tyler Mayer, Joseph S. B. Mitchell, Ojas Parekh, and Cynthia A. Phillips. Probing a Set of Trajectories to Maximize Captured Information. In 18th International Symposium on Experimental Algorithms (SEA 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 160, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SEA.2020.5,
  author =	{Fekete, S\'{a}ndor P. and Hill, Alexander and Krupke, Dominik and Mayer, Tyler and Mitchell, Joseph S. B. and Parekh, Ojas and Phillips, Cynthia A.},
  title =	{{Probing a Set of Trajectories to Maximize Captured Information}},
  booktitle =	{18th International Symposium on Experimental Algorithms (SEA 2020)},
  pages =	{5:1--5:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-148-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{160},
  editor =	{Faro, Simone and Cantone, Domenico},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2020.5},
  URN =		{urn:nbn:de:0030-drops-120796},
  doi =		{10.4230/LIPIcs.SEA.2020.5},
  annote =	{Keywords: Algorithm engineering, optimization, complexity, approximation, trajectories}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2020.42

Worst-Case Optimal Covering of Rectangles by Disks

Authors: Sándor P. Fekete, Utkarsh Gupta, Phillip Keldenich, Christian Scheffer, and Sahil Shah

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

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 λ ≥ 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…. The proof uses a careful combination of manual and automatic analysis, demonstrating the power of the employed interval arithmetic technique.

Cite as

Sándor P. Fekete, Utkarsh Gupta, Phillip Keldenich, Christian Scheffer, and Sahil Shah. Worst-Case Optimal Covering of Rectangles by Disks. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 42:1-42:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2020.42,
  author =	{Fekete, S\'{a}ndor P. and Gupta, Utkarsh and Keldenich, Phillip and Scheffer, Christian and Shah, Sahil},
  title =	{{Worst-Case Optimal Covering of Rectangles by Disks}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{42:1--42:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.42},
  URN =		{urn:nbn:de:0030-drops-122003},
  doi =		{10.4230/LIPIcs.SoCG.2020.42},
  annote =	{Keywords: Disk covering, critical density, covering coefficient, tight worst-case bound, interval arithmetic, approximation}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2020.43

Minimum Scan Cover with Angular Transition Costs

Authors: Sándor P. Fekete, Linda Kleist, and Dominik Krupke

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

We provide a comprehensive study of a natural geometric optimization problem motivated by questions in the context of satellite communication and astrophysics. 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. 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 Θ(log χ(G)), while for 3D the minimum scan time is not upper bounded by χ(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 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 ≤ χ(G)^c. For general metric cost functions, we provide approximation algorithms whose performance guarantee depend on the arboricity of the graph.

Cite as

Sándor P. Fekete, Linda Kleist, and Dominik Krupke. Minimum Scan Cover with Angular Transition Costs. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2020.43,
  author =	{Fekete, S\'{a}ndor P. and Kleist, Linda and Krupke, Dominik},
  title =	{{Minimum Scan Cover with Angular Transition Costs}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.43},
  URN =		{urn:nbn:de:0030-drops-122014},
  doi =		{10.4230/LIPIcs.SoCG.2020.43},
  annote =	{Keywords: Graph scanning, graph coloring, angular metric, complexity, approximation, scheduling}
}

Document

Media Exposition

DOI: 10.4230/LIPIcs.SoCG.2020.72

Coordinated Particle Relocation with Global Signals and Local Friction (Media Exposition)

Authors: Victor M. Baez, Aaron T. Becker, Sándor P. Fekete, and Arne Schmidt

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

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.

Cite as

Victor M. Baez, Aaron T. Becker, Sándor P. Fekete, and Arne Schmidt. Coordinated Particle Relocation with Global Signals and Local Friction (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 72:1-72:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{baez_et_al:LIPIcs.SoCG.2020.72,
  author =	{Baez, Victor M. and Becker, Aaron T. and Fekete, S\'{a}ndor P. and Schmidt, Arne},
  title =	{{Coordinated Particle Relocation with Global Signals and Local Friction}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{72:1--72:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.72},
  URN =		{urn:nbn:de:0030-drops-122305},
  doi =		{10.4230/LIPIcs.SoCG.2020.72},
  annote =	{Keywords: Global control, reconfiguration, geometric algorithms, friction}
}

Document

Media Exposition

DOI: 10.4230/LIPIcs.SoCG.2020.73

Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition)

Authors: Amira Abdel-Rahman, Aaron T. Becker, Daniel E. Biediger, Kenneth C. Cheung, Sándor P. Fekete, Neil A. Gershenfeld, Sabrina Hugo, Benjamin Jenett, Phillip Keldenich, Eike Niehs, Christian Rieck, Arne Schmidt, Christian Scheffer, and Michael Yannuzzi

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

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.

Cite as

Amira Abdel-Rahman, Aaron T. Becker, Daniel E. Biediger, Kenneth C. Cheung, Sándor P. Fekete, Neil A. Gershenfeld, Sabrina Hugo, Benjamin Jenett, Phillip Keldenich, Eike Niehs, Christian Rieck, Arne Schmidt, Christian Scheffer, and Michael Yannuzzi. Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 73:1-73:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{abdelrahman_et_al:LIPIcs.SoCG.2020.73,
  author =	{Abdel-Rahman, Amira and Becker, Aaron T. and Biediger, Daniel E. and Cheung, Kenneth C. and Fekete, S\'{a}ndor P. and Gershenfeld, Neil A. and Hugo, Sabrina and Jenett, Benjamin and Keldenich, Phillip and Niehs, Eike and Rieck, Christian and Schmidt, Arne and Scheffer, Christian and Yannuzzi, Michael},
  title =	{{Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{73:1--73:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.73},
  URN =		{urn:nbn:de:0030-drops-122310},
  doi =		{10.4230/LIPIcs.SoCG.2020.73},
  annote =	{Keywords: Finite automata, reconfiguration, construction, scaling}
}

@InProceedings{abdelrahman_et_al:LIPIcs.SoCG.2020.73,
  author =	{Abdel-Rahman, Amira and Becker, Aaron T. and Biediger, Daniel E. and Cheung, Kenneth C. and Fekete, S\'{a}ndor P. and Gershenfeld, Neil A. and Hugo, Sabrina and Jenett, Benjamin and Keldenich, Phillip and Niehs, Eike and Rieck, Christian and Schmidt, Arne and Scheffer, Christian and Yannuzzi, Michael},
  title =	{{Space Ants: Constructing and Reconfiguring Large-Scale Structures with Finite Automata}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{73:1--73:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.73},
  URN =		{urn:nbn:de:0030-drops-122310},
  doi =		{10.4230/LIPIcs.SoCG.2020.73},
  annote =	{Keywords: Finite automata, reconfiguration, construction, scaling}
}

Document

Media Exposition

DOI: 10.4230/LIPIcs.SoCG.2020.74

How to Make a CG Video (Media Exposition)

Authors: Aaron T. Becker and Sándor P. Fekete

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

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.

Cite as

Aaron T. Becker and Sándor P. Fekete. How to Make a CG Video (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 74:1-74:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2020.74,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P.},
  title =	{{How to Make a CG Video}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{74:1--74:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.74},
  URN =		{urn:nbn:de:0030-drops-122328},
  doi =		{10.4230/LIPIcs.SoCG.2020.74},
  annote =	{Keywords: Videos, animation, education, SoCG Multimedia}
}

Document

Media Exposition

DOI: 10.4230/LIPIcs.SoCG.2020.75

Covering Rectangles by Disks: The Video (Media Exposition)

Authors: Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract

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.

Cite as

Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer. Covering Rectangles by Disks: The Video (Media Exposition). In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 75:1-75:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2020.75,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip and Scheffer, Christian},
  title =	{{Covering Rectangles by Disks: The Video}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{75:1--75:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.75},
  URN =		{urn:nbn:de:0030-drops-122337},
  doi =		{10.4230/LIPIcs.SoCG.2020.75},
  annote =	{Keywords: Disk covering, critical density, covering coefficient, tight worst-case bound, interval arithmetic, approximation}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2019.35

Packing Disks into Disks with Optimal Worst-Case Density

Authors: Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

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 <= 1/2 can always be packed into a disk of area 1; on the other hand, for any epsilon>0 there are sets of disks of area 1/2+epsilon 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.

Cite as

Sándor P. Fekete, Phillip Keldenich, and Christian Scheffer. Packing Disks into Disks with Optimal Worst-Case Density. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2019.35,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip and Scheffer, Christian},
  title =	{{Packing Disks into Disks with Optimal Worst-Case Density}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{35:1--35:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.35},
  URN =		{urn:nbn:de:0030-drops-104398},
  doi =		{10.4230/LIPIcs.SoCG.2019.35},
  annote =	{Keywords: Disk packing, packing density, tight worst-case bound, interval arithmetic, approximation}
}

Document

Multimedia Exposition

DOI: 10.4230/LIPIcs.SoCG.2019.63

Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition)

Authors: Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Sebastian Morr, and Christian Scheffer

Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)

Abstract

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).

Cite as

Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Sebastian Morr, and Christian Scheffer. Packing Geometric Objects with Optimal Worst-Case Density (Multimedia Exposition). In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 63:1-63:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2019.63,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Morr, Sebastian and Scheffer, Christian},
  title =	{{Packing Geometric Objects with Optimal Worst-Case Density}},
  booktitle =	{35th International Symposium on Computational Geometry (SoCG 2019)},
  pages =	{63:1--63:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-104-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{129},
  editor =	{Barequet, Gill and Wang, Yusu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.63},
  URN =		{urn:nbn:de:0030-drops-104678},
  doi =		{10.4230/LIPIcs.SoCG.2019.63},
  annote =	{Keywords: Packing, complexity, bounds, packing density}
}

Document

DOI: 10.4230/DagRep.8.8.48

Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 18331)

Authors: Spring Berman, Sándor P. Fekete, Matthew J. Patitz, and Christian Scheideler

Published in: Dagstuhl Reports, Volume 8, Issue 8 (2019)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 18331,"Algorithmic Foundations of Programmable Matter", a new and emerging field that combines theoretical work on algorithms with a wide spectrum of practical applications that reach all the way from small-scale embedded systems to cyber-physical structures at nano-scale. The aim of this seminar was to bring together researchers from computational geometry, distributed computing, DNA computing, and swarm robotics who have worked on programmable matter to inform one another about the newest developments in each area and to discuss future models, approaches, and directions for new research. Similar to the first Dagstuhl seminar on programmable matter (16271), we did focus on some basic problems, but also considered new problems that were now within reach to be studied. During this seminar, we were able to achieve a previously unmatched level of intensity of collaboration, in part due to using a new electronic and interactive web-based platform. This has also allowed for continued research among the attendees based on the work begun during the seminar.

Cite as

Spring Berman, Sándor P. Fekete, Matthew J. Patitz, and Christian Scheideler. Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 18331). In Dagstuhl Reports, Volume 8, Issue 8, pp. 48-66, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@Article{berman_et_al:DagRep.8.8.48,
  author =	{Berman, Spring and Fekete, S\'{a}ndor P. and Patitz, Matthew J. and Scheideler, Christian},
  title =	{{ Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 18331)}},
  pages =	{48--66},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2019},
  volume =	{8},
  number =	{8},
  editor =	{Berman, Spring and Fekete, S\'{a}ndor P. and Patitz, Matthew J. and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.8.48},
  URN =		{urn:nbn:de:0030-drops-102352},
  doi =		{10.4230/DagRep.8.8.48},
  annote =	{Keywords: computational geometry, distributed algorithms, DNA computing, programmable matter, swarm robotics}
}

Document

Invited Talk

DOI: 10.4230/LIPIcs.DISC.2018.1

Autonomous Vehicles: From Individual Navigation to Challenges of Distributed Swarms (Invited Talk)

Authors: Sándor P. Fekete

Published in: LIPIcs, Volume 121, 32nd International Symposium on Distributed Computing (DISC 2018)

Abstract

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).

Cite as

Sándor P. Fekete. Autonomous Vehicles: From Individual Navigation to Challenges of Distributed Swarms (Invited Talk). In 32nd International Symposium on Distributed Computing (DISC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 121, p. 1:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{fekete:LIPIcs.DISC.2018.1,
  author =	{Fekete, S\'{a}ndor P.},
  title =	{{Autonomous Vehicles: From Individual Navigation to Challenges of Distributed Swarms}},
  booktitle =	{32nd International Symposium on Distributed Computing (DISC 2018)},
  pages =	{1:1--1:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-092-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{121},
  editor =	{Schmid, Ulrich and Widder, Josef},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2018.1},
  URN =		{urn:nbn:de:0030-drops-97904},
  doi =		{10.4230/LIPIcs.DISC.2018.1},
  annote =	{Keywords: Autonomous vehicles, interaction, robot swarms, game theory}
}

Document

DOI: 10.4230/LIPIcs.SoCG.2018.29

Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch

Authors: Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, and Henk Meijer

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract

We present a number of breakthroughs for coordinated motion planning, in which the objective is to reconfigure a swarm of labeled convex objects by a combination of parallel, continuous, collision-free translations into a given target arrangement. Problems of this type can be traced back to the classic work of Schwartz and Sharir (1983), who gave a method for deciding the existence of a coordinated motion for a set of disks between obstacles; their approach is polynomial in the complexity of the obstacles, but exponential in the number of disks. Despite a broad range of other non-trivial results for multi-object motion planning, previous work has largely focused on sequential schedules, in which one robot moves at a time, with objectives such as the number of moves; attempts to minimize the overall makespan of a coordinated parallel motion schedule (with many robots moving simultaneously) have defied all attempts at establishing the complexity in the absence of obstacles, as well as the existence of efficient approximation methods. We resolve these open problems by developing a framework that provides constant-factor approximation algorithms for minimizing the execution time of a coordinated, parallel motion plan for a swarm of robots in the absence of obstacles, provided their arrangement entails some amount of separability. In fact, our algorithm achieves constant stretch factor: 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). Various extensions include unlabeled robots and different classes of robots. We also resolve the complexity of finding a reconfiguration plan with minimal execution time by proving that this is NP-hard, even for a grid arrangement without any stationary obstacles. On the other hand, we show that for densely packed disks that cannot be well separated, a stretch factor Omega(N^{1/4}) may be required. On the positive side, we establish a stretch factor of O(N^{1/2}) even in this case. The intricate difficulties of computing precise optimal solutions are demonstrated by the seemingly simple case of just two disks, which is shown to be excruciatingly difficult to solve to optimality.

Cite as

Erik D. Demaine, Sándor P. Fekete, Phillip Keldenich, Christian Scheffer, and Henk Meijer. Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 29:1-29:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{demaine_et_al:LIPIcs.SoCG.2018.29,
  author =	{Demaine, Erik D. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Scheffer, Christian and Meijer, Henk},
  title =	{{Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.29},
  URN =		{urn:nbn:de:0030-drops-87423},
  doi =		{10.4230/LIPIcs.SoCG.2018.29},
  annote =	{Keywords: Robot swarms, coordinated motion planning, parallel motion, makespan, bounded stretch, complexity, approximation}
}

@InProceedings{demaine_et_al:LIPIcs.SoCG.2018.29,
  author =	{Demaine, Erik D. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Scheffer, Christian and Meijer, Henk},
  title =	{{Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{29:1--29:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.29},
  URN =		{urn:nbn:de:0030-drops-87423},
  doi =		{10.4230/LIPIcs.SoCG.2018.29},
  annote =	{Keywords: Robot swarms, coordinated motion planning, parallel motion, makespan, bounded stretch, complexity, approximation}
}

Document

Multimedia Exposition

DOI: 10.4230/LIPIcs.SoCG.2018.74

Coordinated Motion Planning: The Video (Multimedia Exposition)

Authors: Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin, and Christian Scheffer

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract

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.

Cite as

Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Matthias Konitzny, Lillian Lin, and Christian Scheffer. Coordinated Motion Planning: The Video (Multimedia Exposition). In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 74:1-74:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2018.74,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Konitzny, Matthias and Lin, Lillian and Scheffer, Christian},
  title =	{{Coordinated Motion Planning: The Video}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{74:1--74:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.74},
  URN =		{urn:nbn:de:0030-drops-87872},
  doi =		{10.4230/LIPIcs.SoCG.2018.74},
  annote =	{Keywords: Motion planning, robot swarms, complexity, stretch, approximation}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.11

Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces

Authors: Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, and Arne Schmidt

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract

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 can bond when being 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 N^(1/3); for tree-shaped structures, we give an N^(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 path from a given start point.

Cite as

Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, and Arne Schmidt. Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.ISAAC.2017.11,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Krupke, Dominik and Rieck, Christian and Scheffer, Christian and Schmidt, Arne},
  title =	{{Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.11},
  URN =		{urn:nbn:de:0030-drops-82214},
  doi =		{10.4230/LIPIcs.ISAAC.2017.11},
  annote =	{Keywords: Programmable matter, micro-factories, tile assembly, tilt, approximation, hardness}
}

@InProceedings{becker_et_al:LIPIcs.ISAAC.2017.11,
  author =	{Becker, Aaron T. and Fekete, S\'{a}ndor P. and Keldenich, Phillip and Krupke, Dominik and Rieck, Christian and Scheffer, Christian and Schmidt, Arne},
  title =	{{Tilt Assembly: Algorithms for Micro-Factories that Build Objects with Uniform External Forces}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.11},
  URN =		{urn:nbn:de:0030-drops-82214},
  doi =		{10.4230/LIPIcs.ISAAC.2017.11},
  annote =	{Keywords: Programmable matter, micro-factories, tile assembly, tilt, approximation, hardness}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2017.31

Conflict-Free Coloring of Intersection Graphs

Authors: Sándor P. Fekete and Phillip Keldenich

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract

A conflict-free k-coloring of a graph G=(V,E) 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 conflict-free coloring of geometric intersection graphs. We demonstrate that the intersection graph of n geometric objects without fatness properties and size restrictions may have conflict-free chromatic number in \Omega(log n/log log n) and in \Omega(\sqrt{\log n}) for disks or squares of different sizes; it is known for general graphs that the worst case is in \Theta(log^2 n). For unit-disk intersection graphs, we prove that it is NP-complete to decide the existence of a conflict-free coloring with one color; we also show that six colors always suffice, using an algorithm that colors unit disk graphs of restricted height with two colors. We conjecture that four colors are sufficient, which we prove for unit squares instead of unit disks. For interval graphs, we establish a tight worst-case bound of two.

Cite as

Sándor P. Fekete and Phillip Keldenich. Conflict-Free Coloring of Intersection Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 31:1-31:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ISAAC.2017.31,
  author =	{Fekete, S\'{a}ndor P. and Keldenich, Phillip},
  title =	{{Conflict-Free Coloring of Intersection Graphs}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{31:1--31:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.31},
  URN =		{urn:nbn:de:0030-drops-82162},
  doi =		{10.4230/LIPIcs.ISAAC.2017.31},
  annote =	{Keywords: conflict-free coloring, intersection graphs, unit disk graphs, complexity, worst-case bounds}
}

Document

Multimedia Contribution

DOI: 10.4230/LIPIcs.SoCG.2017.62

Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution)

Authors: Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, and An Nguyen

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract

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.

Cite as

Aaron T. Becker, Mustapha Debboun, Sándor P. Fekete, Dominik Krupke, and An Nguyen. Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost (Multimedia Contribution). In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 62:1-62:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SoCG.2017.62,
  author =	{Becker, Aaron T. and Debboun, Mustapha and Fekete, S\'{a}ndor P. and Krupke, Dominik and Nguyen, An},
  title =	{{Zapping Zika with a Mosquito-Managing Drone: Computing Optimal Flight Patterns with Minimum Turn Cost}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{62:1--62:5},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.62},
  URN =		{urn:nbn:de:0030-drops-72394},
  doi =		{10.4230/LIPIcs.SoCG.2017.62},
  annote =	{Keywords: Covering tours, turn cost, complexity, exact optimization}
}

Document

DOI: 10.4230/LIPIcs.ISAAC.2016.32

Universal Guard Problems

Authors: Sándor P. Fekete, Qian Li, Joseph S. B. Mitchell, and Christian Scheffer

Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)

Abstract

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.

Cite as

Sándor P. Fekete, Qian Li, Joseph S. B. Mitchell, and Christian Scheffer. Universal Guard Problems. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.ISAAC.2016.32,
  author =	{Fekete, S\'{a}ndor P. and Li, Qian and Mitchell, Joseph S. B. and Scheffer, Christian},
  title =	{{Universal Guard Problems}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{32:1--32:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Hong, Seok-Hee},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.32},
  URN =		{urn:nbn:de:0030-drops-68022},
  doi =		{10.4230/LIPIcs.ISAAC.2016.32},
  annote =	{Keywords: Art Gallery Problem, universal guarding, polygonization, worst-case bounds, robust covering}
}

Document

DOI: 10.4230/LIPIcs.SOCG.2015.16

Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals

Authors: Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract

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.

Cite as

Aaron T. Becker, Erik D. Demaine, Sándor P. Fekete, Hamed Mohtasham Shad, and Rose Morris-Wright. Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 16-18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{becker_et_al:LIPIcs.SOCG.2015.16,
  author =	{Becker, Aaron T. and Demaine, Erik D. and Fekete, S\'{a}ndor P. and Shad, Hamed Mohtasham and Morris-Wright, Rose},
  title =	{{Tilt: The Video - Designing Worlds to Control Robot Swarms with Only Global Signals}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{16--18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.16},
  URN =		{urn:nbn:de:0030-drops-50870},
  doi =		{10.4230/LIPIcs.SOCG.2015.16},
  annote =	{Keywords: Particle swarms, global control, complexity, geometric computation}
}

Fekete, Sándor

Document

DOI: 10.4230/DagRep.13.2.183

Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 23091)

Authors: Aaron Becker, Sándor Fekete, Irina Kostitsyna, Matthew J. Patitz, Damien Woods, and Ioannis Chatzigiannakis

Published in: Dagstuhl Reports, Volume 13, Issue 2 (2023)

Abstract

This report documents the program and the outcomes of Dagstuhl Seminar 23091, "Algorithmic Foundations of Programmable Matter", a new and emerging field that combines theoretical work on algorithms with a wide spectrum of practical applications that reach all the way from small-scale embedded systems to cyber-physical structures at nano-scale. The aim of this seminar was to bring together researchers from computational geometry, distributed computing, DNA computing, and swarm robotics who have worked on programmable matter to inform one another about the newest developments in each area and to discuss future models, approaches, and directions for new research. Similar to the first two Dagstuhl Seminars on programmable matter (16271 and 18331), we did focus on some basic problems, but also considered new problems that were now within reach to be studied.

Cite as

Aaron Becker, Sándor Fekete, Irina Kostitsyna, Matthew J. Patitz, Damien Woods, and Ioannis Chatzigiannakis. Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 23091). In Dagstuhl Reports, Volume 13, Issue 2, pp. 183-198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{becker_et_al:DagRep.13.2.183,
  author =	{Becker, Aaron and Fekete, S\'{a}ndor and Kostitsyna, Irina and Patitz, Matthew J. and Woods, Damien and Chatzigiannakis, Ioannis},
  title =	{{Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 23091)}},
  pages =	{183--198},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2023},
  volume =	{13},
  number =	{2},
  editor =	{Becker, Aaron and Fekete, S\'{a}ndor and Kostitsyna, Irina and Patitz, Matthew J. and Woods, Damien and Chatzigiannakis, Ioannis},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.13.2.183},
  URN =		{urn:nbn:de:0030-drops-191848},
  doi =		{10.4230/DagRep.13.2.183},
  annote =	{Keywords: computational geometry, distributed algorithms, DNA computing, programmable matter, swarm robotics}
}

Document

DOI: 10.4230/DagRep.6.7.1

Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 16271)

Authors: Sándor Fekete, Andréa W. Richa, Kay Römer, and Christian Scheideler

Published in: Dagstuhl Reports, Volume 6, Issue 7 (2016)

Abstract

his report documents the program and the outcomes of Dagstuhl Seminar 16271 "Algorithmic Foundations of Programmable Matter", a new and emerging field that combines theoretical work on algorithms with a wide spectrum of practical applications that reach all the way from small-scale embedded systems to cyber-physical structures at nano-scale. The aim of the Dagstuhl seminar was to bring together researchers from the algorithms community with selected experts from robotics and distributed systems in order to set a solid base for the development of models, technical solutions, and algorithms that can control programmable matter. Both communities benefited from such a meeting for the following reasons: - Meeting experts from other fields provided additional insights, challenges and focus when considering work on programmable matter. - Interacting with colleagues in a close and social manner gave many starting points for continuing collaboration. - Getting together in a strong, large and enthusiastic group provided the opportunity to plan a number of followup activities. In the following, we provide details and activities of this successful week.

Cite as

Sándor Fekete, Andréa W. Richa, Kay Römer, and Christian Scheideler. Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 16271). In Dagstuhl Reports, Volume 6, Issue 7, pp. 1-14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Article{fekete_et_al:DagRep.6.7.1,
  author =	{Fekete, S\'{a}ndor and Richa, Andr\'{e}a W. and R\"{o}mer, Kay and Scheideler, Christian},
  title =	{{Algorithmic Foundations of Programmable Matter (Dagstuhl Seminar 16271)}},
  pages =	{1--14},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2016},
  volume =	{6},
  number =	{7},
  editor =	{Fekete, S\'{a}ndor and Richa, Andr\'{e}a W. and R\"{o}mer, Kay and Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagRep.6.7.1},
  URN =		{urn:nbn:de:0030-drops-67599},
  doi =		{10.4230/DagRep.6.7.1},
  annote =	{Keywords: distributed algorithms, distributed systems, programmable matter, robotics, self-organization}
}

Document

Complete Volume

DOI: 10.4230/LIPIcs.SoCG.2016

LIPIcs, Volume 51, SoCG'16, Complete Volume

Authors: Sándor Fekete and Anna Lubiw

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract

LIPIcs, Volume 51, SoCG'16, Complete Volume

Cite as

32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@Proceedings{fekete_et_al:LIPIcs.SoCG.2016,
  title =	{{LIPIcs, Volume 51, SoCG'16, Complete Volume}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016},
  URN =		{urn:nbn:de:0030-drops-60580},
  doi =		{10.4230/LIPIcs.SoCG.2016},
  annote =	{Keywords: Analysis of Algorithms and Problem Complexity, Nonnumerical Algorithms and Problems – Geometrical problems and computations, Discrete Mathematics, Combinatorics, Computer Graphics, Computational Geometry and Object Modeling}
}

Document

Front Matter

DOI: 10.4230/LIPIcs.SoCG.2016.0

Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors

Authors: Sándor Fekete and Anna Lubiw

Published in: LIPIcs, Volume 51, 32nd International Symposium on Computational Geometry (SoCG 2016)

Abstract

Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors

Cite as

32nd International Symposium on Computational Geometry (SoCG 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 51, pp. 0:i-0:xviii, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:LIPIcs.SoCG.2016.0,
  author =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  title =	{{Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors}},
  booktitle =	{32nd International Symposium on Computational Geometry (SoCG 2016)},
  pages =	{0:i--0:xviii},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-009-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{51},
  editor =	{Fekete, S\'{a}ndor and Lubiw, Anna},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2016.0},
  URN =		{urn:nbn:de:0030-drops-59658},
  doi =		{10.4230/LIPIcs.SoCG.2016.0},
  annote =	{Keywords: Front Matter, Table of Contents, Foreword, Conference Organization, External Reviewers, Sponsors}
}

Document

DOI: 10.4230/DagSemProc.09371.1

09371 Abstracts Collection – Algorithmic Methods for Distributed Cooperative Systems

Authors: Sándor Fekete, Stefan Fischer, Martin Riedmiller, and Suri Dubhash

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract

From 06.09.09 to 11.09.09 the Dagstuhl Seminar 09371 ``Algorithmic Methods for Distributed Cooperative Systems'' was held in Schloss Dagstuhl~--~Leibniz Center for Informatics. The purpose of this workshop was to bring together researchers from different disciplines whose central interest is in both algorithmic foundations and application scenarios of distributed cooperative systems. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Sándor Fekete, Stefan Fischer, Martin Riedmiller, and Suri Dubhash. 09371 Abstracts Collection – Algorithmic Methods for Distributed Cooperative Systems. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.09371.1,
  author =	{Fekete, S\'{a}ndor and Fischer, Stefan and Riedmiller, Martin and Dubhash, Suri},
  title =	{{09371 Abstracts Collection – Algorithmic Methods for Distributed Cooperative Systems}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--16},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.1},
  URN =		{urn:nbn:de:0030-drops-25224},
  doi =		{10.4230/DagSemProc.09371.1},
  annote =	{Keywords: Algorithms, cooperative systems, sensor networks, multi-robot systems, applications}
}

Document

DOI: 10.4230/DagSemProc.09371.4

On the Fairness of Probabilistic Schedulers for Population Protocols

Authors: Ioannis Chatzigiannakis, Shlomi Dolev, Sándor Fekete, Othon Michail, and Paul Spirakis

Published in: Dagstuhl Seminar Proceedings, Volume 9371, Algorithmic Methods for Distributed Cooperative Systems (2010)

Abstract

We propose a novel, generic definition of emph{probabilistic schedulers} for population protocols. We design two new schedulers, the emph{State Scheduler} and the emph{Transition Function Scheduler}. Both possess the significant capability of being emph{protocol-aware}, i.e. they can assign transition probabilities based on information concerning the underlying protocol. We prove that the proposed schedulers, and also the emph{Random Scheduler} that was defined by Angluin et al. cite{AADFP04}, are all fair with probability $1$. We also define and study emph{equivalence} between schedulers w.r.t. emph{performance} and emph{correctness} and prove that there exist fair probabilistic schedulers that are not equivalent w.r.t. to performance and others that are not equivalent w.r.t. correctness. We implement our schedulers using a new tool for simulating population protocols and evaluate their performance from the viewpoint of experimental analysis and verification. We study three representative protocols to verify stability, and compare the experimental time to convergence with the known complexity bounds. We run our experiments from very small to extremely large populations (of up to $10^{8}$ agents). We get very promising results both of theoretical and practical interest.

Cite as

Ioannis Chatzigiannakis, Shlomi Dolev, Sándor Fekete, Othon Michail, and Paul Spirakis. On the Fairness of Probabilistic Schedulers for Population Protocols. In Algorithmic Methods for Distributed Cooperative Systems. Dagstuhl Seminar Proceedings, Volume 9371, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{chatzigiannakis_et_al:DagSemProc.09371.4,
  author =	{Chatzigiannakis, Ioannis and Dolev, Shlomi and Fekete, S\'{a}ndor and Michail, Othon and Spirakis, Paul},
  title =	{{On the Fairness of Probabilistic Schedulers for Population Protocols}},
  booktitle =	{Algorithmic Methods for Distributed Cooperative Systems},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2010},
  volume =	{9371},
  editor =	{S\'{a}ndor Fekete and Stefan Fischer and Martin Riedmiller and Suri Subhash},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09371.4},
  URN =		{urn:nbn:de:0030-drops-24286},
  doi =		{10.4230/DagSemProc.09371.4},
  annote =	{Keywords: Population Protocols, Fairness, Probabilistic Schedulers, Communicating Automata, Sensor Networks, Experimental Evaluation}
}

Document

DOI: 10.4230/DagSemProc.06481.2

Geometric Distance Estimation for Sensor Networks and Unit Disk Graphs

Authors: Sándor Fekete, Alexander Kröller, Carsten Buschmann, and Stefan Fischer

Published in: Dagstuhl Seminar Proceedings, Volume 6481, Geometric Networks and Metric Space Embeddings (2007)

Abstract

We present an approach to estimating distances in sensor networks. It works by counting common neighbors, high values indicating closeness. Such distance estimates are needed in many self-localization algorithms. Other than many other approaches, ours does not rely on special equipment in the devices.

Cite as

Sándor Fekete, Alexander Kröller, Carsten Buschmann, and Stefan Fischer. Geometric Distance Estimation for Sensor Networks and Unit Disk Graphs. In Geometric Networks and Metric Space Embeddings. Dagstuhl Seminar Proceedings, Volume 6481, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06481.2,
  author =	{Fekete, S\'{a}ndor and Kr\"{o}ller, Alexander and Buschmann, Carsten and Fischer, Stefan},
  title =	{{Geometric Distance Estimation for Sensor Networks and Unit Disk Graphs}},
  booktitle =	{Geometric Networks and Metric Space Embeddings},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6481},
  editor =	{Joachim Gudmundsson and Rolf Klein and Giri Narasimhan and Michiel Smid and Alexander Wolff},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06481.2},
  URN =		{urn:nbn:de:0030-drops-10282},
  doi =		{10.4230/DagSemProc.06481.2},
  annote =	{Keywords: Sensor networks, distance estimation, unit disk graphs.}
}

Document

DOI: 10.4230/DagSemProc.06421.1

06421 Abstracts Collection – Robot Navigation

Authors: Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract

From 15.10.06 to 20.10.06, the Dagstuhl Seminar 06421 ``Robot Navigation''generate automatically was held in the International Conference and Research Center (IBFI), Schloss Dagstuhl. During the seminar, several participants presented their current research, and ongoing work and open problems were discussed. Abstracts of the presentations given during the seminar as well as abstracts of seminar results and ideas are put together in this paper. The first section describes the seminar topics and goals in general. Links to extended abstracts or full papers are provided, if available.

Cite as

Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz. 06421 Abstracts Collection – Robot Navigation. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.1,
  author =	{Fekete, S\'{a}ndor and Fleischer, Rudolf and Klein, Rolf and Lopez-Ortiz, Alejandro},
  title =	{{06421 Abstracts Collection – Robot Navigation}},
  booktitle =	{Robot Navigation},
  pages =	{1--12},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.1},
  URN =		{urn:nbn:de:0030-drops-8890},
  doi =		{10.4230/DagSemProc.06421.1},
  annote =	{Keywords: Motion planning, robotics, computational geometry, online algorithms}
}

Document

DOI: 10.4230/DagSemProc.06421.2

06421 Executive Summary – Robot Navigation

Authors: Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract

For quite a number of years, researchers from various fields have studied problems motivated by Robot Navigation. People in Online Algorithms have developed strategies that can deal with the inherent lack of information an autonomous robot encounters, as it sets out to perform a task in an unknown environment. Computational Geometers have obtained many results on the efficient planning of collision-free motions, and on visibility problems. Scientists and engineers in Robotics have perfected real robots to an astounding degree. Economic household robots and artificial pets are now available; more complex robots are able to carry out difficult search-and-rescue and exploration missions. The goal of this seminar is to bring together researchers from robotics, computational geometry, and online algorithms, in order to exchange problems and ideas, and to jointly work towards solutions. The following questions seem crucial. Given the advanced level of technical development, what are the strategic planning problems researchers in robotics need to solve in the next decade? How can real environments and robots be modeled, so that planning problems become tractable by algorithmic methods, and solutions are still significant for applications? In particular, what can be assumed about perception and motion accuracy? We are planning for plenary sessions where members of all groups can present their problems and recent work. In addition, there will be plenty of time for discussions.

Cite as

Sándor Fekete, Rudolf Fleischer, Rolf Klein, and Alejandro Lopez-Ortiz. 06421 Executive Summary – Robot Navigation. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.2,
  author =	{Fekete, S\'{a}ndor and Fleischer, Rudolf and Klein, Rolf and Lopez-Ortiz, Alejandro},
  title =	{{06421 Executive Summary – Robot Navigation}},
  booktitle =	{Robot Navigation},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.2},
  URN =		{urn:nbn:de:0030-drops-8720},
  doi =		{10.4230/DagSemProc.06421.2},
  annote =	{Keywords: Motion planning, robotics, computational geometry, online algorithms}
}

Document

DOI: 10.4230/DagSemProc.06421.8

Polygon Exploration with Discrete Vision

Authors: Sándor Fekete and Christiane Schmidt

Published in: Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007)

Abstract

With the advent of autonomous robots with two- and three-dimensional scanning capabilities, classical visibility-based exploration methods from computational geometry have gained in practical importance. However, real-life laser scanning of useful accuracy does not allow the robot to scan continuously while in motion; instead, it has to stop each time it surveys its environment. This requirement was studied by Fekete, Klein and N"uchter for the subproblem of looking around a corner, but until now has not been considered for whole polygonal regions. We give the first comprehensive algorithmic study for this important algorithmic problem that combines stationary art gallery-type aspects with watchman-type issues in an online scenario. We show that there is a lower bound of $Omega(sqrt{n})$ on the competitive ratio in an orthogonal polygon with holes; we also demonstrate that even for orthoconvex polygons, a competitive strategy can only be achieved for limited aspect ratio $A$, i.e., for a given lower bound on the size of an edge. Our main result is an $O(log A)$-competitive strategy for simple rectilinear polygons, which is best possible up to constants.

Cite as

Sándor Fekete and Christiane Schmidt. Polygon Exploration with Discrete Vision. In Robot Navigation. Dagstuhl Seminar Proceedings, Volume 6421, pp. 1-23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.06421.8,
  author =	{Fekete, S\'{a}ndor and Schmidt, Christiane},
  title =	{{Polygon Exploration with Discrete Vision}},
  booktitle =	{Robot Navigation},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.8},
  URN =		{urn:nbn:de:0030-drops-8714},
  doi =		{10.4230/DagSemProc.06421.8},
  annote =	{Keywords: Searching, scan cost, visibility problems, watchman problems, online searching, competitive strategies, autonomous mobile robots.}
}

Document

DOI: 10.4230/DagSemProc.05361.6

Deterministic boundary recongnition and topology extraction for large sensor networks

Authors: Sándor Fekete, Alexander Kröller, Dennis Pfisterer, and Stefan Fischer

Published in: Dagstuhl Seminar Proceedings, Volume 5361, Algorithmic Aspects of Large and Complex Networks (2006)

Abstract

We present a new framework for the crucial challenge of self-organization of a large sensor network. The basic scenario can be described as follows: Given a large swarm of immobile sensor nodes that have been scattered in a polygonal region, such as a street network. Nodes have no knowledge of size or shape of the environment or the position of other nodes. Moreover, they have no way of measuring coordinates, geometric distances to other nodes, or their direction. Their only way of interacting with other nodes is to send or to receive messages from any node that is within communication range. The objective is to develop algorithms and protocols that allow self-organization of the swarm into large-scale structures that reflect the structure of the street network, setting the stage for global routing, tracking and guiding algorithms. Our algorithms work in two stages: boundary recognition and topology extraction. All steps are strictly deterministic, yield fast distributed algorithms, and make no assumption on the distribution of nodes in the environment, other than sufficient density.

Cite as

Sándor Fekete, Alexander Kröller, Dennis Pfisterer, and Stefan Fischer. Deterministic boundary recongnition and topology extraction for large sensor networks. In Algorithmic Aspects of Large and Complex Networks. Dagstuhl Seminar Proceedings, Volume 5361, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.05361.6,
  author =	{Fekete, S\'{a}ndor and Kr\"{o}ller, Alexander and Pfisterer, Dennis and Fischer, Stefan},
  title =	{{Deterministic boundary recongnition and topology extraction for large sensor networks}},
  booktitle =	{Algorithmic Aspects of Large and Complex Networks},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2006},
  volume =	{5361},
  editor =	{Stefano Leonardi and Friedhelm Meyer auf der Heide and Dorothea Wagner},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05361.6},
  URN =		{urn:nbn:de:0030-drops-5632},
  doi =		{10.4230/DagSemProc.05361.6},
  annote =	{Keywords: Distributed algorithms, sensor networks, boundary recognition, topology extraction}
}

Document

DOI: 10.4230/DagSemProc.05031.27

Searching with an Autonomous Robot

Authors: Sándor Fekete, Rolf Klein, and Andreas Nüchter

Published in: Dagstuhl Seminar Proceedings, Volume 5031, Algorithms for Optimization with Incomplete Information (2005)

Abstract

We discuss online strategies for visibility-based searching for an object hidden behind a corner, using Kurt3D, a real autonomous mobile robot. This task is closely related to a number of well-studied problems. Our robot uses a three-dimensional laser scanner in a stop, scan, plan, go fashion for building a virtual three-dimensional environment. Besides planning trajectories and avoiding obstacles, Kurt3D is capable of identifying objects like a chair. We derive a practically useful and asymptotically optimal strategy that guarantees a competitive ratio of 2, which differs remarkably from the well-studied scenario without the need of stopping for surveying the environment. Our strategy is used by Kurt3D, documented in a separate video.

Cite as

Sándor Fekete, Rolf Klein, and Andreas Nüchter. Searching with an Autonomous Robot. In Algorithms for Optimization with Incomplete Information. Dagstuhl Seminar Proceedings, Volume 5031, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2005)

Copy BibTex To Clipboard

@InProceedings{fekete_et_al:DagSemProc.05031.27,
  author =	{Fekete, S\'{a}ndor and Klein, Rolf and N\"{u}chter, Andreas},
  title =	{{Searching with an Autonomous Robot}},
  booktitle =	{Algorithms for Optimization with Incomplete Information},
  pages =	{1--2},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2005},
  volume =	{5031},
  editor =	{Susanne Albers and Rolf H. M\"{o}hring and Georg Ch. Pflug and R\"{u}diger Schultz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.05031.27},
  URN =		{urn:nbn:de:0030-drops-1919},
  doi =		{10.4230/DagSemProc.05031.27},
  annote =	{Keywords: Searching , visibility problems , watchman problems , online searching , competitive strategies , autonomous mobile robots three-dimensional laser scanning , Kurt3D}
}

Search Results

Documents authored by Fekete, Sándor P.

Fekete, Sándor P.

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Fekete, Sándor

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Abstract

Cite as

Thanks for your feedback!

Could not send message