Publications (7)
Highway Hull Revisited
Greg Aloupis, Jean Cardinal, Sebastien Collette +4
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 distanc…
Entropy, Triangulation, and Point Location in Planar Subdivisions
Sebastien Collette, Vida Dujmovic, John Iacono +2
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 tim…
Reconfiguration of 3D Crystalline Robots Using O(log n) Parallel Moves
Greg Aloupis, Sebastien Collette, Erik D. Demaine +3
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…
Confluent Persistence Revisited
Sebastien 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…
Cauchy's Arm Lemma on a Growing Sphere
Zachary Abel, David Charlton, Sebastien Collette +6
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 en…
Detecting all regular polygons in a point set
Greg Aloupis, Jean Cardinal, Sebastien Collette +2
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 num…
On the Stretch Factor of Convex Delaunay Graphs
Prosenjit Bose, Paz Carmi, Sebastien Collette +1
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 define…