journal.bib

@comment{{This file has been generated by bib2bib 1.99}}

@comment{{Command line: bib2bib -s year -r -c '$type = "ARTICLE"' bibtexfiles/secollet.bib}}

@article{CCIKLST12a,
  author = {J. Cardinal and S. Collette and H. Ito and M. Korman and S. Langerman and H. Sakaidani and P. Taslakian},
  journal = {Journal of Information Processing},
  title = {Cannibal Animal Games: a new variant of Tic-Tac-Toe},
  volume = {23},
  number = {3},
  pages = {265--271},
  year = {2015}
}

@article{ACCHLO08b,
  abstract = {We introduce the problem of draining water (or balls representing 
water drops) out of a punctured polygon (or a polyhedron) by rotating the 
shape. For 2D polygons, we obtain combinatorial bounds on the number 
of holes needed, both for arbitrary polygons and for special classes of 
polygons. We detail an O(n^2 log n) algorithm that finds the minimum 
number of holes needed for a given polygon, and argue that the complexity 
remains polynomial for polyhedra in 3D. We make a start at characterizing 
the 1-drainable shapes, those that only need one hole. },
  author = {G. Aloupis and J. Cardinal and S. Collette and F. Hurtado and S. Langerman and J. O'Rourke},
  journal = {Computational Geometry: Theory and Applications},
  note = {Special issue of selected papers from the 20th Canadian Conference on Computational Geometry (CCCG'08).},
  title = {Draining a Polygon - or - Rolling a Ball out of a Polygon},
  volume = {47},
  number = {2},
  pages = {316--328},
  year = {2014},
  doi = {10.1016/j.comgeo.2009.08.002}
}

@article{ACCDDDFHHLSST10a,
  abstract = {Given an ordered set of points and an ordered set of geometric objects in the plane, we are interested in finding a non-crossing matching between point-object pairs. In this paper, we address the algorithmic problem of determining whether a non-crossing matching exists between a given point-object pair. We show that when the objects we match the points to are finite point sets, the problem is NP-complete in general, and polynomial when the objects are on a line or when their number is at most 2. When the objects are line segments, we show that the problem is NP-complete in general, and polynomial when the segments form a convex polygon or are all on a line. Finally, for objects that are straight lines, we show that the problem of finding a min-max non-crossing matching is NP-complete.},
  author = {G. Aloupis and J. Cardinal and S. Collette and E. D. Demaine and M. L. Demaine and
M. Dulieu and R. Fabila-Monroy and V. Hart and F. Hurtado and S. Langerman and M. Saumell and
C. Seara and P. Taslakian},
  title = {Non-crossing Matchings of Points with Geometric Objects},
  journal = {Computational Geometry: Theory and Applications},
  volume = {46},
  number = {1},
  pages = {78--92},
  year = {2013},
  doi = {10.1016/j.comgeo.2012.04.005}
}

@article{BCCCKL11b,
  abstract = {We introduce a new geometric spanner whose construction is based on a generalization of the known Stable Roommates problem.
The Stable Roommates Spanner combines the most desirable properties of geometric spanners: a natural definition, small degree, linear number of edges, strong $(1+\varepsilon)$-spanner, 
low weight ($O(1)\ \times$ the weight of the minimum spanning tree) and an efficient construction algorithm. It is an improvement over the well-known Yao graph and $\Theta$-graph and their variants.
We show how to construct such a spanner in $O(n \log^{10} n)$.
Finally, we show how to construct a variant of the Stable Roommates Spanner called the Stable Roommates $\Theta$-Spanner in $O(n \log^{2} n)$. This variant possesses all the properties of the Stable
Roommates Spanner except that it is no longer a strong spanner.},
  author = {P. Bose and P. Carmi and L. Chaitman and S. Collette and M. Katz and S. Langerman},
  title = {Stable Roommates Spanner},
  journal = {Computational Geometry: Theory and Applications},
  note = {Special issue of selected papers from the 22nd Canadian Conference on Computational Geometry (CCCG'10). },
  volume = {46},
  number = {2},
  pages = {120--130},
  year = {2013}
}

@article{BCHKLSS12a,
  author = {P. Bose and S. Collette and F. Hurtado and M. Korman and S. Langerman and V. Sacrist\'an and M. Saumell},
  title = {Some properties of $k$-Delaunay and $k$-Gabriel graphs},
  journal = {Computational Geometry: Theory and Applications},
  volume = {46},
  number = {2},
  pages = {131--139},
  year = {2013},
  note = {Special issue of selected papers from the 22nd Canadian Conference on Computational Geometry (CCCG'10). }
}

@article{CDILM09b,
  abstract = {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 constant factor of optimal. More specifically, an algorithm is presented that preprocesses a connected planar subdivision G of size n and a query distribution D to produce a point location data structure for G. The expected number of point-line comparisons performed by this data structure, when the queries are distributed according to D, is H + O(H^2/3+1) where H=H(G,D) is a lower bound on the expected number of point-line comparisons performed by any linear decision tree for point location in G under the query distribution D. The preprocessing algorithm runs in O(n log n) time and produces a data structure of size O(n). These results are obtained by creating a Steiner triangulation of G that has near-minimum entropy.},
  author = {S. Collette and V. Dujmovi\'c and J. Iacono and S. Langerman and P. Morin},
  journal = {ACM Transactions on Algorithms},
  title = {Entropy, Triangulation, and Point Location in Planar Subdivisions},
  volume = {8},
  number = {3},
  pages = {29},
  year = {2012},
  doi = {10.1145/2229163.2229173}
}

@article{ACDDEFLOPRSW09a,
  abstract = {In this paper we propose novel algorithms for reconfiguring modular robots that are composed of n atoms. Each atom has the shape of a unit cube and can expand/contract each face by half a unit, as well as attach to or detach from faces of neighboring atoms. For universal reconfiguration, atoms must be arranged in 2󫎾 modules. We respect certain physical constraints: each atom reaches at most constant velocity and can displace at most a constant number of other atoms. We assume that one of the atoms has access to the coordinates of atoms in the target configuration.
Our algorithms involve a total of O(n2) atom operations, which are performed in O(n) parallel steps. This improves on previous reconfiguration algorithms, which either use O(n^2) parallel	steps or do not	respect the constraints mentioned above. In fact, in the setting considered, our algorithms are optimal. A further advantage of our algorithms is that reconfiguration can take place within the union of the source and target configuration space, and only requires local communication.},
  author = {G. Aloupis and S. Collette and M. Damian and E. Demaine and D. El-Khechen and R. Flatland and S. Langerman and J. O'Rourke and V. Pinciu and S. Ramaswami and V. Sacristan and S. Wuhrer},
  journal = {Robotica},
  volume = 29,
  number = 1,
  pages = {59 -- 71},
  title = {Efficient Constant-Velocity Reconfiguration of Crystalline Robots},
  doi = {10.1017/S026357471000072X},
  year = {2011}
}

@article{ACCIKLSST10a,
  author = {G. Aloupis and J. Cardinal and S. Collette and S. Imahori and M. Korman and S. Langerman and O. Schwartz and S. Smorodinsky and P. Taslakian},
  title = {Colorful Strips},
  journal = {Graphs and Combinatorics},
  volume = {27},
  number = {3},
  pages = {327--339},
  year = {2011},
  doi = {10.1007/s00373-011-1014-5},
  note = {Special issue of selected papers from the 7th Japan Conference on Computational Geometry and Graphs (JCCGG09).}
}

@article{ABBCDHKLPW09b,
  abstract = {
	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. As an application, we settle the next open case of the Big Line or Big Clique Conjecture of K\'ara, P\'or, and Wood [Discrete Comput. Geom. 34(3):497--506, 2005].},
  author = {Z. Abel and B. Ballinger and P. Bose and S. Collette and V. Dujmovi\'c and F. Hurtado and S. D. Kominers and S. Langerman and A. P\'or and D. R. Wood},
  title = {Every Large Point Set contains Many Collinear Points or an Empty Pentagon},
  journal = {Graphs and Combinatorics},
  year = {2011},
  volume = 27,
  number = 1,
  pages = {47-60},
  doi = {10.1007/s00373-010-0957-2}
}

@article{BCCS08c,
  abstract = {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 the 
Voronoi diagram of S with respect to the convex distance function 
defined by C. We prove that DG_C(S) is a t-spanner for S, 
for some constant t that depends only on the shape of the set C. 
Thus, for any two points p and q in S, the graph DG_C(S) 
contains a path between p and q whose Euclidean length is at most 
t times the Euclidean distance between p and q.},
  author = {P. Bose and P. Carmi and S. Collette and M. Smid},
  pages = {41 -- 56},
  volume = 1,
  number = 1,
  pdf = {http://jocg.org/index.php/jocg/article/view/5/9},
  title = {On the Stretch Factor of Convex Delaunay Graphs},
  journal = {Journal of Computational Geometry},
  year = {2010}
}

@article{ACCLOR09a,
  author = {G. Aloupis and J. Cardinal and S. Collette and S. Langerman and D. Orden and P. Ramos},
  title = {Decomposition of Multiple Coverings into More Parts},
  journal = {Discrete and Computational Geometry},
  pages = {706-723},
  volume = {44},
  issue = {3},
  doi = {10.1007/s00454-009-9238-3},
  abstract = {We prove that for every centrally symmetric convex polygon Q, there exists a constant ? such that any locally finite ? k-fold covering of the plane by translates of Q can be decomposed into k coverings. This improves on a quadratic upper bound proved by Pach and T髏h. The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery life.},
  year = {2010}
}

@article{ACCHLOP08b,
  abstract = {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 points is the minimum time required to move from one point to the other, with optional use of H. 
The highway hull HH(S,H) of a point set S is the minimal set containing S as well as the shortest paths between all pairs of points in HH(S,H), using the highway time distance. 
We provide a Theta(n log n) worst-case time algorithm to find the highway hull under the L_1 metric, as well as an O(n log^2 n) time algorithm for the L_2 metric which improves the best known result of O(n^2). 
We also define and construct the useful region of the plane: the region that a highway must intersect in order that the shortest path between at least one pair of points uses the highway.},
  author = {G. Aloupis and J. Cardinal and S. Collette and F. Hurtado and S. Langerman and J. O'Rourke and B. Palop},
  title = {Highway Hull Revisited},
  journal = {Computational Geometry: Theory and Applications},
  volume = {43},
  year = {2010},
  pages = {115--130},
  doi = {10.1016/j.comgeo.2009.06.001}
}

@article{BCLMMS06a,
  abstract = {We introduce and analyze sigma-local graphs, based on a definition of locality by Erickson. We present two algorithms to construct such graphs, for any real number sigma>1 and any set S of n points. These algorithms run in time O(sigma^{d} n + n log n) for sets in R^d and O(n log^3 n  log log n + k) for sets in the plane, where k is the size of the output. 

Algorithms to find the minimum or maximum sigma such that the corresponding graph has properties such as connectivity, planarity, and no-isolated vertex are presented, with complexities in O(n polylog n). These algorithms can also be used to efficiently construct the corresponding graphs.},
  author = {P. Bose and S. Collette and S. Langerman and A. Maheshwari and P. Morin and M. Smid},
  journal = {Journal of Discrete Algorithms},
  title = {Sigma-Local Graphs},
  doi = {10.1016/j.jda.2008.10.002},
  volume = {8},
  number = {1},
  pages = {15--23},
  year = {2010}
}

@article{ACDDFLORSW08a,
  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 x 2 x 2 meta-modules.  The reconfiguration involves a total of O(n) atom operations (expand, contract, attach, detach) and is performed in O(n) parallel steps.  This improves on previous reconfiguration algorithms, which require O(n^2) parallel steps.  Our algorithm is in place; that is, the reconfiguration takes place within the union of the bounding boxes of the source and target robots. We show that the algorithm can also be implemented in a synchronous, distributed fashion.},
  author = {G. Aloupis and S. Collette and M. Damian and E. D. Demaine and R. Flatland and S. Langerman and J. O'Rourke and S. Ramaswami and V. Sacristan and S. Wuhrer},
  title = {Linear Reconfiguration of Cube-Style Modular Robots},
  journal = {Computational Geometry: Theory and Applications},
  volume = {42},
  pages = {652--663},
  doi = {10.1016/j.comgeo.2008.11.003},
  year = {2009}
}

@article{ACCLS07b,
  abstract = {We study several coloring problems for geometric range-spaces. In
addition to their theoretical interest, some of these problems
arise in sensor networks. Given a set of points in R^2
or R^3, we want to color them such that every region of
a certain family (e.g.,~every disk containing at least a certain
number of points) contains points of many different colors. In
this paper, we think of the number of colors and the number of
points as functions of k. Obviously, for a fixed k using k
colors, it is not always possible to ensure that every region
containing k points has all colors present. Thus, we introduce
two types of relaxations: either we allow the number of colors to
increase to c(k), or we require that the number of points in
each region increases to p(k).

Symmetrically, given a finite set of regions  in R^2 or
R^3, we want to color them such that every point
covered by a sufficiently large number of regions is contained in
regions of k different colors.  This requires the number of
covering regions or the number of allowed colors to be greater
than k.

The goal of this paper is to bound these two functions for several
types of region families, such as halfplanes, halfspaces, disks
and pseudo-disks. We improve and generalize previous results of
Pach, Tardos and T\'oth on decompositions of space coverings.},
  author = {G. Aloupis and J. Cardinal and S. Collette and S. Langerman and S. Smorodinsky},
  journal = {Discrete and Computational Geometry},
  title = {Coloring Geometric Range Spaces},
  year = {2009},
  volume = {41},
  pages = {348-362},
  doi = {10.1007/s00454-008-9116-4}
}

@article{CCL06b,
  abstract = { A family of proximity graphs, called Empty Region Graphs (ERG)
is
presented. The vertices of an ERG are points in the plane, and two points are
connected if their neighborhood, defined by a region, does not contain any other
point. The region defining the neighborhood of two points is a parameter of the
graph. This way of defining graphs is not new, and ERGs include several known proximity graphs such as
Nearest Neighbor Graphs, Beta-Skeletons or Theta-Graphs. The main contribution is to provide insight and connections between the definition of ERG and the properties of the corresponding graphs. 

We give conditions on the region defining an
ERG to ensure a number of properties that might be desirable in applications, such as planarity, connectivity, triangle-freeness, cycle-freeness, bipartiteness and
bounded degree. These conditions take the form of what we call tight
regions: maximal or minimal regions that a region must contain or be contained
in to make the graph satisfy a given property. We show that every monotone property has at least one corresponding tight region; we discuss possibilities and
limitations of this general model for constructing a graph from a point set.},
  author = {J. Cardinal and S. Collette and S. Langerman},
  journal = {Computational Geometry: Theory and Applications},
  title = {Empty Region Graphs},
  year = {2009},
  pages = {183-195},
  volume = {42},
  doi = {10.1016/j.comgeo.2008.09.003}
}

@article{CCHLP07c,
  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 travel speed is high. More specifically, one can travel from one endpoint of the walkway to the other at speed v>1, but can only travel at unit speed between any other pair of points. The travel time between any two points in the plane is the minimum between the actual geometric distance, and the time needed to go from one point to the other using the walkway. A location for a walkway is said to be optimal with respect to a given finite set of points if it minimizes the maximum travel time between any two points of the set. We give a simple linear-time algorithm for finding an optimal location in the case where the points are on a line. We also give an Omega(n log n) lower bound for the problem of computing the travel time diameter of a set of n points on a line with respect to a given walkway. Then we describe an O(n log n) algorithm for locating a walkway with the additional restriction that the walkway must be horizontal. This algorithm is based on a recent generic method for solving quasiconvex programs with implicitly defined constraints. It is used in a (1+epsilon)-approximation algorithm for optimal location of a walkway of arbitrary orientation. },
  author = {J. Cardinal and S. Collette and F. Hurtado and S. Langerman and B. Palop},
  journal = {Computational Geometry: Theory and Applications},
  pages = {219--229},
  volume = {41},
  doi = {10.1016/j.comgeo.2008.01.001},
  title = {Optimal Location of Transportation Devices},
  year = {2008}
}

@article{CCG06b,
  abstract = {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 time-complexity of the
feasibility problem of these systems is linear relatively to
the number of (sporadic) tasks for a fixed number of
processors. We propose a scheduling algorithm theoretically
optimal (i.e., preemptions and migrations neglected).
Moreover, we provide an exact feasibility utilization
bound. Lastly, we propose a technique to limit the number of
migrations and preemptions.},
  author = {S. Collette and L. Cucu and J. Goossens},
  journal = {Information Processing Letters},
  title = {Integrating Job Parallelism in Real-Time Scheduling Theory},
  pages = {180--187},
  volume = 106,
  year = {2008},
  doi = {10.1016/j.ipl.2007.11.014}
}

@article{CCL06,
  abstract = {We propose a definition of locality for properties of geometric graphs. 
We measure the local density of graphs using region-counting distances between pairs of vertices, and we use this density to define local properties of classes of graphs.

We illustrate locality by introducing the local diameter of geometric graphs: we define it as the upper bound on the size of the shortest path between any pair of vertices, expressed as a function of the density of the graph around these vertices. 
We determine the local diameter of several well-studied graphs such as Theta-graphs, Ordered Theta-graphs and Skip List Spanners. We also show that various operations, such as path and point queries using geometric graphs as data structures, have complexities which can be expressed as local properties.},
  author = {J. Cardinal and S. Collette and S. Langerman},
  journal = {Computational Geometry: Theory and Applications},
  volume = {39},
  pages = {55--64},
  number = {1},
  note = {Special issue of selected papers from the 16th Canadian Conference on Computational Geometry (CCCG'04).},
  pdf = {http://www.ulb.ac.be/di/algo/secollet/papers/ccl06.pdf},
  doi = {10.1016/j.comgeo.2007.05.011},
  title = {Local Properties of Geometric Graphs},
  year = {2008}
}

@comment{{This file has been generated by bib2bib 1.99}}

@comment{{Command line: bib2bib -s year -r -c '$type = "ARTICLE"' bibtexfiles/secollet-future.bib}}