Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves (2009)
Aloupis, Greg, Collette, Sebastien, Demaine, Erik D., Langerman, Stefan, Sacristan, Vera, Wuhrer, Stefanie
We consider the theoretical model of Crystalline robots, which have been introduced and prototyped by the robotics community. These robots consist of independently manipulable unit-square atoms that...
Detecting all regular polygons in a point set (2009)
Aloupis, Greg, Cardinal, Jean, Collette, Sebastien, Iacono, John, Langerman, Stefan
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...
Entropy, Triangulation, and Point Location in Planar Subdivisions (2009)
Collette, Sebastien, Dujmovic, Vida, Iacono, John, Langerman, Stefan, Morin, Pat
A data structure is presented for point location in connected planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that is within a...
Aloupis, Greg, Cardinal, Jean, Collette, Sebastien, Hurtado, Ferran, Langerman, Stefan, O'Rourke, Joseph, ...
A highway H is a line in the plane on which one can travel at a greater speed than in the remaining plane. One can choose to enter and exit H at any point. The highway time distance between a pair of...
Cauchy's Arm Lemma on a Growing Sphere (2008)
Abel, Zachary, Charlton, David, Collette, Sebastien, Demaine, Erik D., Demaine, Martin L., Langerman, Stefan, ...
We propose a variant of Cauchy's Lemma, proving that when a convex chain on one sphere is redrawn (with the same lengths and angles) on a larger sphere, the distance between its endpoints increases....
On the Stretch Factor of Convex Delaunay Graphs (2008)
Bose, Prosenjit, Carmi, Paz, Collette, Sebastien, Smid, Michiel
Let C be a compact and convex set in the plane that contains the origin in its interior, and let S be a finite set of points in the plane. The Delaunay graph DG_C(S) of S is defined to be the dual of...