Abstract Region Counting Circles (2009)
Jean Cardinal, Sébastien Collette, Stefan Langerman
The region counting distances, introduced by Demaine, Iacono and Langerman [5], associate to any pair of points p, q the number of items of a dataset S contained in a region R(p, q) surrounding p, q....
Every Large Point Set contains Many Collinear Points or an Empty Pentagon (2009)
Abel, Zachary, Ballinger, Brad, Bose, Prosenjit, Collette, Sébastien, Dujmović, Vida, Hurtado, Ferran, ...
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....
Abstract Region Counting Graphs (2009)
Jean Cardinal, Sébastien Collette, Stefan Langerman
A new family of proximity graphs, called region counting graphs (RCG) is presented. The RCG for a finite set of points in the plane uses the notion of region counting distance introduced by Demaine...
Linear Reconfiguration of Cube-Style Modular Robots (2008)
Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Stefan Langerman, Suneeta Ramaswami, ...
Abstract. In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2 × 2 × 2...
Linear Reconfiguration of Cube-Style Modular Robots (2008)
Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatl, Vera Sacristán, ...
In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2×2×2 meta-modules. The...
Linear Reconfiguration of Cube-Style Modular Robots (2008)
Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Stefan Langerman, Suneeta Ramaswami, ...
Abstract. In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2 × 2 × 2...
Where to build a temple, and where to dig to find one (2008)
Greg Aloupis, Jean Cardinal, Sébastien Collette, John Iacono, Stefan Langerman
In this paper, we analyze the time complexity of finding regular polygons in a set of n points. We use two different approaches to find regular polygons, depending on their number of edges. Those...
DISTRIBUTION-SENSITIVE POINT LOCATION IN CONVEX SUBDIVISIONS ∗ (2008)
Sébastien Collette, John Iacono, Pat Morin, Stefan Langerman
ABSTRACT. A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is...
Linear Reconfiguration of Cube-Style Modular Robots (2008)
Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatl, ...
In this paper we propose a novel algorithm for both contracting and expanding cube-style modular robots which reconfigures any given source robot composed of n atoms into any given target robot with...
Optimal Location of Transportation Devices (2008)
Jean Cardinal, Sébastien Collette, Ferran Hurtado, Stefan Langerman, Belén Palop
Abstract. We consider algorithms for finding the optimal location of a simple transportation device, that we call a moving walkway, consisting of a pair of points in the plane between which the...
Greg Aloupis, Jean Cardinal, Sébastien Collette, Stefan Langerman
Abstract. We analyze a new popular video-game called Lumines, which was developed by Sony for the PSP platform. It involves a sequence of bichromatic 2x2 blocks that fall in a grid and must be...
Distribution-Sensitive Point Location in Convex Subdivisions ∗ Abstract (2008)
Sébastien Collette, Vida Dujmović, John Iacono, Stefan Langerman
A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that differs by only...
Linear Reconfiguration of Cube-Style Modular Robots (2008)
Greg Aloupis, Sébastien Collette, Mirela Damian, Erik D. Demaine, Robin Flatl, Suneeta Ramaswami, ...
Abstract. In this paper we propose a novel algorithm that, given a source robot S and a target robot T, reconfigures S into T. Both S and T are robots composed of n atoms arranged in 2 × 2 × 2...
On the Symbolic Computation of the Hardest Configurations of the RUSH HOUR Game ⋆ (2008)
Sébastien Collette, Jean-françois Raskin, Frédéric Servais
Abstract. RUSH HOUR is a sliding block game where blocks represent cars stuck in a traffic jam on a 6 × 6 board. The goal of the game is to allow one of the cars (the target car) to exit this...
DISTRIBUTION-SENSITIVE POINT LOCATION IN CONVEX SUBDIVISIONS ∗ (2008)
Sébastien Collette, Stefan Langerman, Vida Dujmović, John Iacono, ...
ABSTRACT. A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that...
Abstract Region Counting Circles (2008)
Jean Cardinal, Sébastien Collette, Stefan Langerman
The region counting distances, introduced by Demaine, Iacono and Langerman [5], associate to any pair of points p, q the number of items of a dataset S contained in a region R(p, q) surrounding p, q....
Distribution-Sensitive Point Location in Convex Subdivisions 1 (2008)
Sébastien Collette, Vida Dujmović, John Iacono, Stefan Langerman, Pat Morin
Abstract. A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. If the optimal data structure in the linear decision...
Abstract Sigma-Local Graphs (2008)
Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid
We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [9]. We present two algorithms to construct such graphs, for any real number σ> 1 and any set S of n...
Abstract Sigma-Local Graphs (2008)
Prosenjit Bose, Sébastien Collette, Stefan Langerman, Anil Maheshwari, Pat Morin, Michiel Smid
We introduce and analyze σ-local graphs, based on a definition of locality by Erickson [11]. We present two algorithms to construct such graphs, for any real number σ> 1 and any set S of n...
DISTRIBUTION-SENSITIVE POINT LOCATION IN CONVEX SUBDIVISIONS ∗ (2008)
Sébastien Collette, John Iacono, Pat Morin, Stefan Langerman
ABSTRACT. A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is...
Integrating job parallelism in real-time scheduling theory (2008)
Collette, Sébastien, Cucu, Liliana, Goossens, Joël
We investigate the global scheduling of sporadic, implicit deadline, real-time task systems on multiprocessor platforms. We provide a task model which integrates job parallelism. We prove that the...
Integrating job parallelism in real-time scheduling theory (2008)
Collette, Sébastien, Cucu, Liliana, Goossens, Joël
We investigate the global scheduling of sporadic, implicit deadline, real-time task systems on multiprocessor platforms. We provide a task model which integrates job parallelism. We prove that the...
Regions, Distances and Graphs (2006)
We present new approaches to define and analyze geometric graphs. The region-counting distances, introduced by Demaine, Iacono and Langerman, associate to any pair of points (p,q) the number of items...
Regions, Distances and Graphs (2006)
We present new approaches to define and analyze geometric graphs. The region-counting distances, introduced by Demaine, Iacono and Langerman, associate to any pair of points (p,q) the number of items...
Regions, Distances and Graphs (2006)
We present new approaches to define and analyze geometric graphs. The region-counting distances, introduced by Demaine, Iacono and Langerman, associate to any pair of points (p,q) the number of items...
Regions, Distances and Graphs (2006)
We present new approaches to define and analyze geometric graphs. The region-counting distances, introduced by Demaine, Iacono and Langerman, associate to any pair of points (p,q) the number of items...
Local properties of geometric graphs (2004)
Jean Cardinal, Sébastien Collette, Stefan Langerman
We propose a definition of locality for properties of geometric graphs. We measure the local density of graphs using region-counting distances [8] between pairs of vertices, and we use this density...