Search Results

Documents authored by Scheffer, Christian

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}
}
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
DOI: 10.4230/LIPIcs.ISAAC.2022.67
The Dispersive Art Gallery Problem

Authors: Christian Rieck and Christian Scheffer

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

Abstract
We introduce a new variant of the art gallery problem that comes from safety issues. In this variant we are not interested in guard sets of smallest cardinality, but in guard sets with largest possible distances between these guards. To the best of our knowledge, this variant has not been considered before. We call it the Dispersive Art Gallery Problem. In particular, in the dispersive art gallery problem we are given a polygon 𝒫 and a real number 𝓁, and want to decide whether 𝒫 has a guard set such that every pair of guards in this set is at least a distance of 𝓁 apart. In this paper, we study the vertex guard variant of this problem for the class of polyominoes. We consider rectangular visibility and distances as geodesics in the L₁-metric. Our results are as follows. We give a (simple) thin polyomino such that every guard set has minimum pairwise distances of at most 3. On the positive side, we describe an algorithm that computes guard sets for simple polyominoes that match this upper bound, i.e., the algorithm constructs worst-case optimal solutions. We also study the computational complexity of computing guard sets that maximize the smallest distance between all pairs of guards within the guard sets. We prove that deciding whether there exists a guard set realizing a minimum pairwise distance for all pairs of guards of at least 5 in a given polyomino is NP-complete. We were also able to find an optimal dynamic programming approach that computes a guard set that maximizes the minimum pairwise distance between guards in tree-shaped polyominoes, i.e., computes optimal solutions; due to space constraints, details can be found in the full version of our paper [Christian Rieck and Christian Scheffer, 2022]. Because the shapes constructed in the NP-hardness reduction are thin as well (but have holes), this result completes the case for thin polyominoes.
Cite as

Christian Rieck and Christian Scheffer. The Dispersive Art Gallery Problem. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 67:1-67:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{rieck_et_al:LIPIcs.ISAAC.2022.67,
  author =	{Rieck, Christian and Scheffer, Christian},
  title =	{{The Dispersive Art Gallery Problem}},
  booktitle =	{33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
  pages =	{67:1--67:18},
  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.67},
  URN =		{urn:nbn:de:0030-drops-173522},
  doi =		{10.4230/LIPIcs.ISAAC.2022.67},
  annote =	{Keywords: Art gallery, dispersion, polyominoes, NP-completeness, r-visibility, vertex guards, L₁-metric, worst-case optimal}
}
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
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
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}
}
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/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}
}
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}
}
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.ISAAC.2016.60
Approximate Shortest Distances Among Smooth Obstacles in 3D

Authors: Christian Scheffer and Jan Vahrenhold

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

Abstract
We consider the classic all-pairs-shortest-paths (APSP) problem in a three-dimensional environment where paths have to avoid a set of smooth obstacles whose surfaces are represented by discrete point sets with n sample points in total. We show that if the point sets represent epsilon-samples of the underlying surfaces, (1 ± O(sqrt{epsilon}))-approximations of the distances between all pairs of sample points can be computed in O(n^{5/2} log^2 n) time.
Cite as

Christian Scheffer and Jan Vahrenhold. Approximate Shortest Distances Among Smooth Obstacles in 3D. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 60:1-60:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{scheffer_et_al:LIPIcs.ISAAC.2016.60,
  author =	{Scheffer, Christian and Vahrenhold, Jan},
  title =	{{Approximate Shortest Distances Among Smooth Obstacles in 3D}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{60:1--60: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.60},
  URN =		{urn:nbn:de:0030-drops-68292},
  doi =		{10.4230/LIPIcs.ISAAC.2016.60},
  annote =	{Keywords: Geodesic distances; approximation algorithm; epsilon sample}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2016.26
Approximating the Integral Fréchet Distance

Authors: Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer

Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)

Abstract
We present a pseudo-polynomial time (1 + epsilon)-approximation algorithm for computing the integral and average Fréchet distance between two given polygonal curves T_1 and T_2. The running time is in O(zeta^{4}n^4/epsilon^2) where n is the complexity of T_1 and T_2 and zeta is the maximal ratio of the lengths of any pair of segments from T_1 and T_2. Furthermore, we give relations between weighted shortest paths inside a single parameter cell C and the monotone free space axis of C. As a result we present a simple construction of weighted shortest paths inside a parameter cell. Additionally, such a shortest path provides an optimal solution for the partial Fréchet similarity of segments for all leash lengths. These two aspects are related to each other and are of independent interest.
Cite as

Anil Maheshwari, Jörg-Rüdiger Sack, and Christian Scheffer. Approximating the Integral Fréchet Distance. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{maheshwari_et_al:LIPIcs.SWAT.2016.26,
  author =	{Maheshwari, Anil and Sack, J\"{o}rg-R\"{u}diger and Scheffer, Christian},
  title =	{{Approximating the Integral Fr\'{e}chet Distance}},
  booktitle =	{15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)},
  pages =	{26:1--26:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-011-8},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{53},
  editor =	{Pagh, Rasmus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.26},
  URN =		{urn:nbn:de:0030-drops-60485},
  doi =		{10.4230/LIPIcs.SWAT.2016.26},
  annote =	{Keywords: Fr\'{e}chet distance, partial Fr\'{e}chet similarity, curve matching}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact