SCSébastien Collette

Sébastien Collette

*This is an algorithmically generated author record based on publicly available information.

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


Sébastien Collette has a total of 40 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Cannibal Animal Games: a new variant of Tic-Tac-Toe

    by Jean Cardinal, Sébastien Collette, Hiro Ito, Matias Korman, Stefan Langerman, Hikaru Sakaidani, Perouz Taslakian

    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.

  • Blocking Colored Point Sets

    by Greg Aloupis, Brad Ballinger, Sébastien Collette, Stefan Langerman, Attila Pór, David R. Wood


  • Confluent Persistence Revisited

    by Sébastien Collette, John Iacono, Stefan Langerman

    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

    Efficient constant-velocity reconfiguration of crystalline robots

    by Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatland, Stefan Langerman, Joseph O'Rourke, Val Pinciu, Suneeta Ramaswami, Vera Sacristán, et al.

    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.


  • Every Large Point Set contains Many Collinear Points or an Empty Pentagon

    by Zachary Abel, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmović, Ferran Hurtado, Scott Duke Kominers, Stefan Langerman, Attila Pór, David R. Wood


  • Sigma-local graphs

    by Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid


  • Highway hull revisited

    by Greg Aloupis, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Stefan Langerman, Joseph O'Rourke, Belén Palop


  • Open Access

    Blocking Coloured Point Sets

    by Greg Aloupis, Brad Ballinger, Sébastien Collette, Stefan Langerman, Attila Pór, David R. Wood

    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

    by Greg Aloupis, Jean Cardinal, Sebastien Collette, John Iacono, Stefan Langerman

    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

    by Zachary Abel, Brad Ballinger, Prosenjit Bose, Sébastien Collette, Vida Dujmović, Ferran Hurtado, Scott D. Kominers, Stefan Langerman, Attila Pór, David R. Wood

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