Sébastien Collette
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
Research Interests
Sébastien Collette has a total of 40 co-authors. Here are the top co-authors by number of shared publications:
- Stefan Langerman
Computer Science Department Université Libre de Bruxelles Belgium
11 shared publications - Attila Pór
Department of Mathematics, Western Kentucky University, Bowling Green, USA
4 shared publications - David R. Wood
Monash University, Melbourne, Australia
4 shared publications - Greg Aloupis
Universite Libre de Bruxelles
4 shared publications - Brad Ballinger
Humboldt State University
3 shared publications - Fiama Pierina Orejuela Hurtado
Departament de Matemàtica Aplicada II Universitat Politècnica de Catalunya Barcelona Spain
3 shared publications
Latest Publications
- Open Access
Cannibal Animal Games: a new variant of Tic-Tac-Toe
This paper presents a new partial two-player game, called the \emph{cannibal animal game}, which is a variant of Tic-Tac-Toe. The game is played on the infinite grid, where in each round a player chooses and occupies free cells. The first player Alice can occupy a cell in each turn and wins if she occupies a set of cells, the union of a subset of which is a translated, reflected and/or rotated copy of a previously agreed upon polyomino $P$ (called an \emph{animal}). The objective of the second player Bob is to prevent Alice from creating her animal by occupying in each round a translated, reflected and/or rotated copy of $P$. An animal is a \emph{cannibal} if Bob has a winning strategy, and a \emph{non-cannibal} otherwise. This paper presents some new tools, such as the \emph{bounding strategy} and the \emph{punching lemma}, to classify animals into cannibals or non-cannibals. We also show that the \emph{pairing strategy} works for this problem.Open AccessCannibal Animal Games: a new variant of Tic-Tac-Toe
This paper presents a new partial two-player game, called the \emph{cannibal animal game}, which is a variant of Tic-Tac-Toe. The game is played on the infinite grid, where in each round a player chooses and occupies free cells. The first player Alice can occupy a cell in each turn and wins if she occupies a set of cells, the union of a subset of which is a translated, reflected and/or rotated copy of a previously agreed upon polyomino $P$ (called an \emph{animal}). The objective of the second player Bob is to prevent Alice from creating her animal by occupying in each round a translated, reflected and/or rotated copy of $P$. An animal is a \emph{cannibal} if Bob has a winning strategy, and a \emph{non-cannibal} otherwise. This paper presents some new tools, such as the \emph{bounding strategy} and the \emph{punching lemma}, to classify animals into cannibals or non-cannibals. We also show that the \emph{pairing strategy} works for this problem. - 17 January 2012
- Published by Society for Industrial & Applied Mathematics (SIAM)
Confluent Persistence Revisited
It is shown how to enhance any data structure in the pointer model to make it confluently persistent, with efficient query and update times and limited space overhead. Updates are performed in O(log n) amortized time, and following a pointer takes O(log c log n) time where c is the in-degree of a node in the data structure. In particular, this proves that confluent persistence can be achieved at a logarithmic cost in the bounded in-degree model used widely in previous work. This is a O(n/ log n)-factor improvement over the previous known transform to make a data structure confluently persistenthttp://dx.doi.org/10.1137/1.9781611973099.50info:eu-repo/semantics/publishe
- 17 January 2012
- Published by Society for Industrial & Applied Mathematics (SIAM)
Confluent Persistence Revisited
It is shown how to enhance any data structure in the pointer model to make it confluently persistent, with efficient query and update times and limited space overhead. Updates are performed in O(log n) amortized time, and following a pointer takes O(log c log n) time where c is the in-degree of a node in the data structure. In particular, this proves that confluent persistence can be achieved at a logarithmic cost in the bounded in-degree model used widely in previous work. This is a O(n/ log n)-factor improvement over the previous known transform to make a data structure confluently persistenthttp://dx.doi.org/10.1137/1.9781611973099.50info:eu-repo/semantics/publishe
- Open Access
- 14 January 2011
- Published by Cambridge University Press (CUP) in Robotica
- Vol. 29 (1) , 59-71
Efficient constant-velocity reconfiguration of crystalline robots
SUMMARY: In this paper, we propose novel algorithms for reconfiguring modular robots that are composed ofnatoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or detach from faces of neighboring atoms. For universal reconfiguration, atoms must be arranged in 2 × 2 × 2 modules. We respect certain physical constraints: each atom reaches at most constant velocity and can displace at most a constant number of other atoms. We assume that one of the atoms has access to the coordinates of atoms in the target configuration.Our algorithms involve a total ofO(n2) atom operations, which are performed inO(n) parallel steps. This improves on previous reconfiguration algorithms, which either useO(n2) parallel steps or do not respect the constraints mentioned above. In fact, in the settings considered, our algorithms are optimal. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configuration space, and only requires local communication.
- 14 January 2011
- Published by Cambridge University Press (CUP) in Robotica
- Vol. 29 (1) , 59-71
Open AccessEfficient constant-velocity reconfiguration of crystalline robots
SUMMARY: In this paper, we propose novel algorithms for reconfiguring modular robots that are composed ofnatoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or detach from faces of neighboring atoms. For universal reconfiguration, atoms must be arranged in 2 × 2 × 2 modules. We respect certain physical constraints: each atom reaches at most constant velocity and can displace at most a constant number of other atoms. We assume that one of the atoms has access to the coordinates of atoms in the target configuration.Our algorithms involve a total ofO(n2) atom operations, which are performed inO(n) parallel steps. This improves on previous reconfiguration algorithms, which either useO(n2) parallel steps or do not respect the constraints mentioned above. In fact, in the settings considered, our algorithms are optimal. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configuration space, and only requires local communication.
- 7 October 2010
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 27 (1) , 47-60
Every Large Point Set contains Many Collinear Points or an Empty Pentagon
- 7 October 2010
- Published by Springer Nature in Graphs and Combinatorics
- Vol. 27 (1) , 47-60
Every Large Point Set contains Many Collinear Points or an Empty Pentagon
- 31 March 2010
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 8 (1) , 15-23
Sigma-local graphs
- 31 March 2010
- Published by Elsevier in Journal of Discrete Algorithms
- Vol. 8 (1) , 15-23
Sigma-local graphs
- 28 February 2010
- Published by Elsevier in Computational Geometry
- Vol. 43 (2) , 115-130
Highway hull revisited
- 28 February 2010
- Published by Elsevier in Computational Geometry
- Vol. 43 (2) , 115-130
Highway hull revisited
- Open Access
Blocking Coloured Point Sets
This paper studies problems related to visibility among points in the plane. A point $x$ \emph{blocks} two points $v$ and $w$ if $x$ is in the interior of the line segment $\bar{vw}$. A set of points $P$ is \emph{$k$-blocked} if each point in $P$ is assigned one of $k$ colours, such that distinct points $v,w\in P$ are assigned the same colour if and only if some other point in $P$ blocks $v$ and $w$. The focus of this paper is the conjecture that each $k$-blocked set has bounded size (as a function of $k$). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterise all sets $\{n_1,n_2,n_3,n_4\}$ such that some 4-blocked set has exactly $n_i$ points in the $i$-th colour class. Amongst other results, for infinitely many values of $k$, we construct $k$-blocked sets with $k^{1.79...}$ points.Open AccessBlocking Coloured Point Sets
This paper studies problems related to visibility among points in the plane. A point $x$ \emph{blocks} two points $v$ and $w$ if $x$ is in the interior of the line segment $\bar{vw}$. A set of points $P$ is \emph{$k$-blocked} if each point in $P$ is assigned one of $k$ colours, such that distinct points $v,w\in P$ are assigned the same colour if and only if some other point in $P$ blocks $v$ and $w$. The focus of this paper is the conjecture that each $k$-blocked set has bounded size (as a function of $k$). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterise all sets $\{n_1,n_2,n_3,n_4\}$ such that some 4-blocked set has exactly $n_i$ points in the $i$-th colour class. Amongst other results, for infinitely many values of $k$, we construct $k$-blocked sets with $k^{1.79...}$ points. - Open Access
Detecting all regular polygons in a point set
In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We combine two different approaches to find regular polygons, depending on their number of edges. Our result depends on the parameter alpha, which has been used to bound the maximum number of isosceles triangles that can be formed by n points. This bound has been expressed as O(n^{2+2alpha+epsilon}), and the current best value for alpha is ~0.068. Our algorithm finds polygons with O(n^alpha) edges by sweeping a line through the set of points, while larger polygons are found by random sampling. We can find all regular polygons with high probability in O(n^{2+alpha+epsilon}) expected time for every positive epsilon. This compares well to the O(n^{2+2alpha+epsilon}) deterministic algorithm of Brass.
Open AccessDetecting all regular polygons in a point set
In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We combine two different approaches to find regular polygons, depending on their number of edges. Our result depends on the parameter alpha, which has been used to bound the maximum number of isosceles triangles that can be formed by n points. This bound has been expressed as O(n^{2+2alpha+epsilon}), and the current best value for alpha is ~0.068. Our algorithm finds polygons with O(n^alpha) edges by sweeping a line through the set of points, while larger polygons are found by random sampling. We can find all regular polygons with high probability in O(n^{2+alpha+epsilon}) expected time for every positive epsilon. This compares well to the O(n^{2+2alpha+epsilon}) deterministic algorithm of Brass.
- Open Access
Every Large Point Set contains Many Collinear Points or an Empty Pentagon
We prove the following generalised empty pentagon theorem: for every integer $\ell \geq 2$, every sufficiently large set of points in the plane contains $\ell$ collinear points or an empty pentagon. As an application, we settle the next open case of the "big line or big clique" conjecture of K\'ara, P\'or, and Wood [\emph{Discrete Comput. Geom.} 34(3):497--506, 2005].Open AccessEvery Large Point Set contains Many Collinear Points or an Empty Pentagon
We prove the following generalised empty pentagon theorem: for every integer $\ell \geq 2$, every sufficiently large set of points in the plane contains $\ell$ collinear points or an empty pentagon. As an application, we settle the next open case of the "big line or big clique" conjecture of K\'ara, P\'or, and Wood [\emph{Discrete Comput. Geom.} 34(3):497--506, 2005].