
[1]

J. Cardinal, N. Cohen, S. Collette, M. Hoffmann, S. Langerman, and G. Rote.
Coloring dynamic point sets on a line.
In Proceedings of the 28th European Workshop on Computational
Geometry (EuroCG12), 2012.
[ bib ]

[2]

J. Cardinal, S. Collette, H. Ito, M. Korman, S. Langerman, H. Sakaidani, and
P. Taslakian.
Cannibal animal games: a new variant of tictactoe.
In Proceedings of the 27th European Workshop on Computational
Geometry (EuroCG11), 2011.
4 pages.
[ bib ]

[3]

J. Cardinal, S. Collette, H. Ito, M. Korman, S. Langerman, H. Sakaidani, and
P. Taslakian.
Cannibal animal games: a new variant of tictactoe.
In Proceedings of the 4th Annual Meeting of AAAC (AAAC11),
2011.
2 pages.
[ bib ]

[4]

G. Aloupis, P. Bose, S. Collette, E. D. Demaine, M. L. Demaine, K. Douieb,
V. Dujmovic, J. Iacono, S. Langerman, and P. Morin.
Common unfoldings of polyominoes and polycubes.
In Proceedings of the ChinaJapan Joint Conference on
Computational Geometry, Graphs and Applications (CGGA 2010), 2010.
2 pages.
[ bib ]

[5]

G. Aloupis, B. Ballinger, S. Collette, S. Langerman, A. Por, and D. R. Wood.
Blocking coloured point sets.
In Proceedings of the 26th European Workshop on Computational
Geometry (EuroCG10), 2010.
4 pages.
[ bib ]

[6]

P. Bose, S. Collette, F. Hurtado, M. Korman, S. Langerman, V. Sacristan, and
M. Saumell.
Some Properties of Higher Order Delaunay and Gabriel
Graphs.
In Proceedings of the Canadian Conference on Computational
Geometry (CCCG10), 2010.
4 pages.
[ bib ]
We consider two classes of higher order proximity graphs defined on a set of points in the plane, namely, the kDelaunay graph and the kGabriel graph. We give bounds on the following combinatorial and geometric properties of these graphs: spanning ratio, diameter, chromatic number, and minimum number of layers necessary to partition the edges of the graphs so that no two edges of the same layer cross.

[7]

V. Berten, S. Collette, and J. Goossens.
Feasibility test for multiphase parallel realtime jobs.
In Proceedings of the WorkinProgress session of the IEEE
RealTime Systems Symposium 2009, 2009.
4 pages.
[ bib ]

[8]

G. Aloupis, J. Cardinal, S. Collette, S. Imahori, M. Korman, S. Langerman,
O. Schwartz, S. Smorodinsky, and P. Taslakian.
Colorful strips.
In Proceedings of the 7th Japan Conference on Computational
Geometry and Graphs (JCCGG09), 2009.
2 pages.
[ bib ]

[9]

G. Aloupis, J. Cardinal, S. Collette, E. D. Demaine, M. L. Demaine, M. Dulieu,
R. FabilaMonroy, V. Hart, F. Hurtado, S. Langerman, M. Saumell, C. Seara,
and P. Taslakian.
Matching points with things.
In Proceedings of the 7th Japan Conference on Computational
Geometry and Graphs (JCCGG09), 2009.
2 pages.
[ bib ]

[10]

P. Bose, J. Cardinal, S. Collette, E. D. Demaine, B. Palop, P. Taslakian, and
N. Zeh.
Relaxed Gabriel Graphs.
In Proceedings of the Canadian Conference on Computational
Geometry (CCCG09), 2009.
4 pages.
[ bib ]
We study a new family of geometric graphs that interpolate between the Delaunay triangulation and the Gabriel graph.
These graphs share many properties with βskeletons
for βin[0,1] (such as sublinear spanning ratio)
with the added benefit of planarity
(and consequently linear size and local routability).

[11]

Z. Abel, B. Ballinger, P. Bose, S. Collette, V. Dujmović, F. Hurtado, S. D.
Kominers, S. Langerman, A. Pór, and D. R. Wood.
Every large point set contains many collinear points or an
empty pentagon.
In Proceedings of the Canadian Conference on Computational
Geometry (CCCG09), 2009.
4 pages.
[ bib ]
We prove the following generalised empty pentagon theorem: for every integer >=2, every sufficiently large set of points in the plane contains 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ára, Pór, and Wood [Discrete Comput. Geom. 34(3):497506, 2005].

[12]

G. Aloupis, J. Cardinal, S. Collette, F. Hurtado, S. Langerman, and
J. O'Rourke.
Draining a polygon  or  rolling a ball out of a polygon.
In Proceedings of the Canadian Conference on Computational
Geometry (CCCG08), 2008.
7 pages.
[ bib ]

[13]

G. Aloupis, J. Cardinal, S. Collette, S. Langerman, and S. Smorodinsky.
Coloring geometric range spaces.
In Proceedings of the 24th European Workshop on Computational
Geometry (EuroCG08), 2008.
4 pages.
[ bib ]

[14]

G. Aloupis, S. Collette, M. Damian, E. D. Demaine, R. Flatland, S. Langerman,
J. O'Rourke, S. Ramaswami, V. Sacristan, and S. Wuhrer.
Linear reconfiguration of cubestyle modular robots.
In Proceedings of the XII Encuentros de Geometría
Computacional (EGC'07), 2007.
8 pages.
[ bib ]

[15]

J. Cardinal, S. Collette, F. Hurtado, S. Langerman, and B. Palop.
Moving walkways, escalators, and elevators.
In Proceedings of the XII Encuentros de Geometría
Computacional (EGC'07), 2007.
8 pages.
[ bib ]

[16]

S. Collette, V. Dujmović, J. Iacono, S. Langerman, and P. Morin.
Distributionsensitive point location in convex
subdivisions.
In Proceedings of the 17th Fall Workshop on Computational and
Combinatorial Geometry, 2007.
2 pages.
[ bib ]

[17]

J. Cardinal, S. Collette, F. Hurtado, S. Langerman, and B. Palop.
Moving walkways, escalators, and elevators.
In Proceedings of the Kyoto International Conference on
Computational Geometry and Graph Theory (KyotoCGGT2007), 2007.
2 pages.
[ bib 
http ]
We study a simple geometric model of transportation facility that consists of two points between which the travel speed is high. This elementary definition can model shuttle services, tunnels, bridges, teleportation devices, escalators or moving walkways. The travel time between a pair of points is defined as a time distance, in such a way that a customer uses the transportation facility only if it is helpful. We give algorithms for finding the optimal location of such a transportation facility, where optimality is defined with respect to the maximum travel time between two points in a given set.

[18]

G. Aloupis, J. Cardinal, S. Collette, J. Iacono, and S. Langerman.
Where to build a temple, and where to dig to find one.
In Proceedings of the 22nd European Workshop on Computational
Geometry (EuroCG06), 2006.
4 pages.
[ bib 
.pdf ]
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 with o(n^0.068)
edges are found by sweeping a line through the set of points, while the larger
polygons are found by random sampling. We can find with high probability all
the polygons in O(n^(2.068+epsilon)) expected time for every positive epsilon.
This compares well to the O(n^(2.136+epsilon)) deterministic algorithm of Brass.
Our method can also be used to find incomplete regular polygons, where up to a
constant fraction of the vertices are missing.

[19]

J. Cardinal, S. Collette, and S. Langerman.
Region counting circles.
In Proceedings of the Canadian Conference on Computational
Geometry (CCCG05), pages 278281, 2005.
4 pages.
[ bib 
.pdf ]
The region counting distances, introduced by Demaine, Iacono
and Langerman, 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. We define
region counting disks and circles, and study the complexity of these objects.
In particular, we prove that for some wide class of regions R(p,q),
the complexity of a region counting circle of radius k is either at least as
large as the complexity of the klevel in an arrangement of lines, or
is linear in S. We give a complete characterization of regions falling
into one of these two cases. Algorithms to compute εapproximations
of region counting distances and approximations of region counting circles are
presented.

[20]

J. Cardinal, S. Collette, and S. Langerman.
Region counting graphs.
In Proceedings of the 21st European Workshop on Computational
Geometry (EuroCG05), 2005.
4 pages.
[ bib 
.pdf ]
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 et al.
to characterize the proximity between two points p and q: the
edge pq is in the RCG if and only if there is less than or exactly k
vertices in a given geometric neighborhood defined by a region.
These graphs generalize many common proximity graphs, such as
knearest neighbor graphs, Betaskeletons or Thetagraphs.
This paper concentrates on RCGs that are invariant under translations,
rotations and uniform scaling.
For k=0, we give conditions on regions R that define an RCG to
ensure a number of properties including
planarity, connectivity, triangle freeness, cycle freeness,
bipartiteness, and bounded degree. These conditions take
form of what we call tight regions: maximal or minimal regions
that a region R must contain or be contained in to satisfy a given
monotone property.

[21]

J. Cardinal, S. Collette, and S. Langerman.
Local properties of geometric graphs.
In Proceedings of the Canadian Conference on Computational
Geometry (CCCG04), 2004.
4 pages.
[ bib 
.pdf ]
We introduce a new property for geometric graphs: the local
diameter. This property is based on the use of the region
counting distances introduced by Demaine, Iacono and Langerman as a
generalization of the rank difference. We use it as a
characterization of the local density of the vertices. We study the
properties of those distances, and show that there is a strong
relation between region counting distances and speed distances. We
define the local diameter as the upper bound on the length of the
shortest path between any pair of vertices, expressed as a function of
the number of vertices in their neighborhood. We determine the local
diameter of several wellstudied graphs such as the Ordered
Thetagraph and the Skip List Spanner. We also analyze the impact
of the local diameter for different applications, such as path and
point queries on geometric graphs.