[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 tic-tac-toe. 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 tic-tac-toe. 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 China-Japan 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 k-Delaunay graph and the k-Gabriel 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 multi-phase parallel real-time jobs. In Proceedings of the Work-in-Progress session of the IEEE Real-Time 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. Fabila-Monroy, 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):497--506, 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 cube-style 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. Distribution-sensitive 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 ]
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 278--281, 2005. 4 pages. [ bib ]
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 k-level 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 ]
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 k-nearest neighbor graphs, Beta-skeletons or Theta-graphs. 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 ]
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 well-studied graphs such as the Ordered Theta-graph 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.