7 Search Results for "Peters, Tom"

Document
DOI: 10.4230/LIPIcs.ISAAC.2024.33
Robust Bichromatic Classification Using Two Lines

Authors: Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, and Frank Staals

Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)

Abstract
Given two sets R and B of n points in the plane, we present efficient algorithms to find a two-line linear classifier that best separates the "red" points in R from the "blue" points in B and is robust to outliers. More precisely, we find a region 𝒲_B bounded by two lines, so either a halfplane, strip, wedge, or double wedge, containing (most of) the blue points B, and few red points. Our running times vary between optimal O(nlog n) up to around O(n³), depending on the type of region 𝒲_B and whether we wish to minimize only red outliers, only blue outliers, or both.
Cite as

Erwin Glazenburg, Thijs van der Horst, Tom Peters, Bettina Speckmann, and Frank Staals. Robust Bichromatic Classification Using Two Lines. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 33:1-33:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{glazenburg_et_al:LIPIcs.ISAAC.2024.33,
  author =	{Glazenburg, Erwin and van der Horst, Thijs and Peters, Tom and Speckmann, Bettina and Staals, Frank},
  title =	{{Robust Bichromatic Classification Using Two Lines}},
  booktitle =	{35th International Symposium on Algorithms and Computation (ISAAC 2024)},
  pages =	{33:1--33:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-354-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{322},
  editor =	{Mestre, Juli\'{a}n and Wirth, Anthony},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.33},
  URN =		{urn:nbn:de:0030-drops-221605},
  doi =		{10.4230/LIPIcs.ISAAC.2024.33},
  annote =	{Keywords: Geometric Algorithms, Separating Line, Classification, Bichromatic, Duality}
}
Document
DOI: 10.4230/LIPIcs.ITP.2024.35
Formal Verification of the Empty Hexagon Number

Authors: Bernardo Subercaseaux, Wojciech Nawrocki, James Gallicchio, Cayden Codel, Mario Carneiro, and Marijn J. H. Heule

Published in: LIPIcs, Volume 309, 15th International Conference on Interactive Theorem Proving (ITP 2024)

Abstract
A recent breakthrough in computer-assisted mathematics showed that every set of 30 points in the plane in general position (i.e., no three points on a common line) contains an empty convex hexagon. Heule and Scheucher solved this problem with a combination of geometric insights and automated reasoning techniques by constructing CNF formulas ϕ_n, with O(n⁴) clauses, such that if ϕ_n is unsatisfiable then every set of n points in general position must contain an empty convex hexagon. An unsatisfiability proof for n = 30 was then found with a SAT solver using 17 300 CPU hours of parallel computation. In this paper, we formalize and verify this result in the Lean theorem prover. Our formalization covers ideas in discrete computational geometry and SAT encoding techniques by introducing a framework that connects geometric objects to propositional assignments. We see this as a key step towards the formal verification of other SAT-based results in geometry, since the abstractions we use have been successfully applied to similar problems. Overall, we hope that our work sets a new standard for the verification of geometry problems relying on extensive computation, and that it increases the trust the mathematical community places in computer-assisted proofs.
Cite as

Bernardo Subercaseaux, Wojciech Nawrocki, James Gallicchio, Cayden Codel, Mario Carneiro, and Marijn J. H. Heule. Formal Verification of the Empty Hexagon Number. In 15th International Conference on Interactive Theorem Proving (ITP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 309, pp. 35:1-35:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{subercaseaux_et_al:LIPIcs.ITP.2024.35,
  author =	{Subercaseaux, Bernardo and Nawrocki, Wojciech and Gallicchio, James and Codel, Cayden and Carneiro, Mario and Heule, Marijn J. H.},
  title =	{{Formal Verification of the Empty Hexagon Number}},
  booktitle =	{15th International Conference on Interactive Theorem Proving (ITP 2024)},
  pages =	{35:1--35:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-337-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{309},
  editor =	{Bertot, Yves and Kutsia, Temur and Norrish, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2024.35},
  URN =		{urn:nbn:de:0030-drops-207633},
  doi =		{10.4230/LIPIcs.ITP.2024.35},
  annote =	{Keywords: Empty Hexagon Number, Discrete Computational Geometry, Erd\H{o}s-Szekeres}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2024.89
Optimal In-Place Compaction of Sliding Cubes (Media Exposition)

Authors: Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes. This note accompanies a video that explains our in-place algorithm for reconfiguration in the sliding cubes model. Specifically, our algorithm [Irina Kostitsyna et al., 2023] reconfigures any n-cube configuration into a compact canonical shape using a number of moves proportional to the sum of coordinates of the input cubes. As is common in the literature, we can then reconfigure between two arbitrary shapes via their canonical configurations. The number of moves performed by our algorithm is asymptotically worst-case optimal and strictly improves upon the current state-of-the-art.
Cite as

Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann. Optimal In-Place Compaction of Sliding Cubes (Media Exposition). In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 89:1-89:4, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SoCG.2024.89,
  author =	{Kostitsyna, Irina and Ophelders, Tim and Parada, Irene and Peters, Tom and Sonke, Willem and Speckmann, Bettina},
  title =	{{Optimal In-Place Compaction of Sliding Cubes}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{89:1--89:4},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.89},
  URN =		{urn:nbn:de:0030-drops-200347},
  doi =		{10.4230/LIPIcs.SoCG.2024.89},
  annote =	{Keywords: Sliding cubes, Reconfiguration algorithm, Modular robots}
}
Document
DOI: 10.4230/LIPIcs.SWAT.2024.31
Optimal In-Place Compaction of Sliding Cubes

Authors: Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann

Published in: LIPIcs, Volume 294, 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)

Abstract
The sliding cubes model is a well-established theoretical framework that supports the analysis of reconfiguration algorithms for modular robots consisting of face-connected cubes. As is common in the literature, we focus on reconfiguration via an intermediate canonical shape. Specifically, we present an in-place algorithm that reconfigures any n-cube configuration into a compact canonical shape using a number of moves proportional to the sum of coordinates of the input cubes. This result is asymptotically optimal and strictly improves on all prior work. Furthermore, our algorithm directly extends to dimensions higher than three.
Cite as

Irina Kostitsyna, Tim Ophelders, Irene Parada, Tom Peters, Willem Sonke, and Bettina Speckmann. Optimal In-Place Compaction of Sliding Cubes. In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 294, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.SWAT.2024.31,
  author =	{Kostitsyna, Irina and Ophelders, Tim and Parada, Irene and Peters, Tom and Sonke, Willem and Speckmann, Bettina},
  title =	{{Optimal In-Place Compaction of Sliding Cubes}},
  booktitle =	{19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2024)},
  pages =	{31:1--31:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-318-8},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{294},
  editor =	{Bodlaender, Hans L.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2024.31},
  URN =		{urn:nbn:de:0030-drops-200713},
  doi =		{10.4230/LIPIcs.SWAT.2024.31},
  annote =	{Keywords: Sliding cubes, Reconfiguration algorithm, Modular robots}
}
Document
DOI: 10.4230/LIPIcs.DISC.2023.27
Fast Reconfiguration for Programmable Matter

Authors: Irina Kostitsyna, Tom Peters, and Bettina Speckmann

Published in: LIPIcs, Volume 281, 37th International Symposium on Distributed Computing (DISC 2023)

Abstract
The concept of programmable matter envisions a very large number of tiny and simple robot particles forming a smart material. Even though the particles are restricted to local communication, local movement, and simple computation, their actions can nevertheless result in the global change of the material’s physical properties and geometry. A fundamental algorithmic task for programmable matter is to achieve global shape reconfiguration by specifying local behavior of the particles. In this paper we describe a new approach for shape reconfiguration in the amoebot model. The amoebot model is a distributed model which significantly restricts memory, computing, and communication capacity of the individual particles. Thus the challenge lies in coordinating the actions of particles to produce the desired behavior of the global system. Our reconfiguration algorithm is the first algorithm that does not use a canonical intermediate configuration when transforming between arbitrary shapes. We introduce new geometric primitives for amoebots and show how to reconfigure particle systems, using these primitives, in a linear number of activation rounds in the worst case. In practice, our method exploits the geometry of the symmetric difference between input and output shape: it minimizes unnecessary disassembly and reassembly of the particle system when the symmetric difference between the initial and the target shapes is small. Furthermore, our reconfiguration algorithm moves the particles over as many parallel shortest paths as the problem instance allows.
Cite as

Irina Kostitsyna, Tom Peters, and Bettina Speckmann. Fast Reconfiguration for Programmable Matter. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 27:1-27:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.DISC.2023.27,
  author =	{Kostitsyna, Irina and Peters, Tom and Speckmann, Bettina},
  title =	{{Fast Reconfiguration for Programmable Matter}},
  booktitle =	{37th International Symposium on Distributed Computing (DISC 2023)},
  pages =	{27:1--27:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-301-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{281},
  editor =	{Oshman, Rotem},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2023.27},
  URN =		{urn:nbn:de:0030-drops-191533},
  doi =		{10.4230/LIPIcs.DISC.2023.27},
  annote =	{Keywords: Programmable matter, amoebot model, shape reconfiguration}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.41
Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities

Authors: Tom Demeulemeester and Jannik Peters

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
We study relationships between different relaxed notions of core stability in hedonic games. In particular, we study (i) q-size core stable outcomes in which no deviating coalition of size at most q exists and (ii) k-improvement core stable outcomes in which no coalition can improve by a factor of more than k. For a large class of hedonic games, including fractional and additively separable hedonic games, we derive upper bounds on the maximum factor by which a coalition of a certain size can improve in a q-size core stable outcome. We further provide asymptotically tight lower bounds for a large class of hedonic games. Finally, our bounds allow us to confirm two conjectures by Fanelli et al. [Angelo Fanelli et al., 2021][IJCAI'21] for symmetric fractional hedonic games (S-FHGs): (i) every q-size core stable outcome in an S-FHG is also q/(q-1)-improvement core stable and (ii) the price of anarchy of q-size stability in S-FHGs is precisely 2q/q-1.
Cite as

Tom Demeulemeester and Jannik Peters. Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 41:1-41:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{demeulemeester_et_al:LIPIcs.MFCS.2023.41,
  author =	{Demeulemeester, Tom and Peters, Jannik},
  title =	{{Relaxed Core Stability for Hedonic Games with Size-Dependent Utilities}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{41:1--41:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.41},
  URN =		{urn:nbn:de:0030-drops-185759},
  doi =		{10.4230/LIPIcs.MFCS.2023.41},
  annote =	{Keywords: hedonic games, core stability, algorithmic game theory, computational social choice}
}
Document
Brief Announcement
DOI: 10.4230/LIPIcs.DISC.2022.47
Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter

Authors: Irina Kostitsyna, Tom Peters, and Bettina Speckmann

Published in: LIPIcs, Volume 246, 36th International Symposium on Distributed Computing (DISC 2022)

Abstract
The concept of programmable matter envisions a very large number of tiny and simple robot particles forming a smart material that can change its physical properties and shape based on the outcome of computation and movement performed by the individual particles in a concurrent manner. We use geometric insights to develop a new type of shortest path tree for programmable matter systems. Our feather trees utilize geometry to allow particles and information to traverse the programmable matter structure via shortest paths even in the presence of multiple overlapping trees.
Cite as

Irina Kostitsyna, Tom Peters, and Bettina Speckmann. Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter. In 36th International Symposium on Distributed Computing (DISC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 246, pp. 47:1-47:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kostitsyna_et_al:LIPIcs.DISC.2022.47,
  author =	{Kostitsyna, Irina and Peters, Tom and Speckmann, Bettina},
  title =	{{Brief Announcement: An Effective Geometric Communication Structure for Programmable Matter}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{47:1--47:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2022.47},
  URN =		{urn:nbn:de:0030-drops-172386},
  doi =		{10.4230/LIPIcs.DISC.2022.47},
  annote =	{Keywords: Programmable matter, amoebot model, shape reconfiguration}
}
  • Refine by Author
  • 5 Peters, Tom
  • 5 Speckmann, Bettina
  • 4 Kostitsyna, Irina
  • 2 Ophelders, Tim
  • 2 Parada, Irene
  • Show More...

  • Refine by Classification

  • Refine by Keyword
  • 2 Modular robots
  • 2 Programmable matter
  • 2 Reconfiguration algorithm
  • 2 Sliding cubes
  • 2 amoebot model
  • Show More...

  • Refine by Type
  • 7 document

  • Refine by Publication Year
  • 4 2024
  • 2 2023
  • 1 2022

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 About DROPS Imprint Privacy Contact