techrep.bib

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

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

@techreport{BCCHKLT12a,
  abstract = {Given an arrangement of lines in the plane, what is the minimum number $c$ of colors required to color the lines so that no cell of the arrangement is monochromatic? In this paper we give bounds on the number c both for the above question, as well as some of its variations. We redefine these problems as geometric hypergraph coloring problems. If we define $\Hlinecell$ as the hypergraph where vertices are lines and edges represent cells of the arrangement, the answer to the above question is equal to the chromatic number of this hypergraph. We prove that this chromatic number is between $\Omega (\log n / \log\log n)$. and $O(\sqrt{n})$. 
Similarly, we give bounds on the minimum size of a subset $S$ of the intersections of the lines in $\mathcal{A}$ such that every cell is bounded by at least one of the vertices in $S$. This may be seen as a problem on guarding cells with vertices when the lines act as obstacles. The problem can also be defined as the minimum vertex cover problem in the hypergraph $\Hvertexcell$, the vertices of which are the line intersections, and the hyperedges are vertices of a cell. Analogously, we consider the problem of touching the lines with a minimum subset of the cells of the arrangement, which we identify as the minimum vertex cover problem in the $\Hcellzone$ hypergraph.},
  author = {P. Bose and J. Cardinal and S. Collette and F. Hurtado and M. Korman and S. Langerman and P. Taslakian},
  title = {Coloring and Guarding Arrangements},
  institution = {arXiv, Cornell University},
  number = {arXiv:1205.5162},
  year = {2012},
  pdf = {http://arxiv.org/abs/1205.5162},
  note = {13 pages}
}

@techreport{BCFL11a,
  abstract = {We present a general method for de-amortizing essentially any Binary Search Tree (BST) algorithm. In particular, by transforming Splay Trees, our method produces a BST that has the same asymptotic cost as Splay Trees on any access sequence while performing each search in $O(\log n)$ worst case time. By transforming Multi-Splay Trees, we obtain a BST that is $O(\log \log n)$ competitive, satisfies the scanning theorem, the static optimality theorem, the static finger theorem, the working set theorem, and performs each search in $O(\log n)$ worst case time. Moreover, we prove that if there is a dynamically optimal BST algorithm, then there is a dynamically optimal BST algorithm that answers every search in $O(\log n)$ worst case time.},
  author = {P. Bose and S. Collette and R. Fagerberg and S. Langerman},
  title = {De-amortizing Binary Search Trees},
  institution = {arXiv, Cornell University},
  number = {arXiv:1111.1665},
  year = {2011},
  pdf = {http://arxiv.org/abs/1111.1665},
  note = {14 pages}
}

@techreport{CIL11a,
  abstract = {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 performed in $O(\log n)$ amortized time, and following a pointer takes $O(\log c \log n)$ time where $c$ is the in-degree of a node in the data structure. In particular, this proves that confluent persistence can be achieved at a logarithmic cost in the bounded in-degree model used widely in previous work. This is a $O(n/\log n)$-factor improvement over the previous known transform to make a data structure confluently persistent.},
  author = {S. Collette and J. Iacono and S. Langerman},
  title = {Confluent Persistence Revisited},
  institution = {arXiv, Cornell University},
  number = {arXiv:1104.3045},
  year = {2011},
  pdf = {http://arxiv.org/abs/1104.3045},
  note = {15 pages}
}

@techreport{BCFL12a,
  abstract = {We present a general method for de-amortizing essentially any Binary Search Tree (BST) algorithm. In particular, by transforming Splay Trees, our method produces a BST that has the same asymptotic cost as Splay Trees on any access sequence while performing each search in $O(\log n)$ worst case time. By transforming Multi-Splay Trees, we obtain a BST that is $O(\log \log n)$ competitive, satisfies the scanning theorem, the static optimality theorem, the static finger theorem, the working set theorem, and performs each search in $O(\log n)$ worst case time. Moreover, we prove that if there is a dynamically optimal BST algorithm, then there is a dynamically optimal BST algorithm that answers every search in $O(\log n)$ worst case time.},
  author = {P. Bose and S. Collette and R. Fagerberg and S. Langerman},
  title = {De-amortizing Binary Search Trees},
  institution = {arXiv, Cornell University},
  number = {arXiv:1111.1665},
  year = {2011},
  pdf = {http://arxiv.org/abs/1111.1665},
  note = {14 pages}
}

@techreport{ABCLPW10b,
  abstract = {This paper studies problems related to visibility among points in the plane. A point $x$ \emph{blocks} two points $v$ and $w$ if $x$ is in the interior of the line segment $\bar{vw}$. A set of points $P$ is \emph{$k$-blocked} if each point in $P$ is assigned one of $k$ colours, such that distinct points $v,w\in P$ are assigned the same colour if and only if some other point in $P$ blocks $v$ and $w$. The focus of this paper is the conjecture that each $k$-blocked set has bounded size (as a function of $k$). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterise all sets $\{n_1,n_2,n_3,n_4\}$ such that some 4-blocked set has exactly $n_i$ points in the $i$-th colour class. Amongst other results, for infinitely many values of $k$, we construct $k$-blocked sets with $k^{1.79...}$ points.},
  author = {G. Aloupis and B. Ballinger and S. Collette and S. Langerman and A. Por and D. R. Wood},
  title = {Blocking Coloured Point Sets},
  institution = {arXiv, Cornell University},
  number = {arXiv:1002.0190},
  year = {2010},
  pdf = {http://arxiv.org/abs/	1002.0190},
  note = {17 pages}
}

@techreport{ACDLSW09a,
  abstract = {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 can extend/contract arms on each side and attach/detach from neighbors. These operations suffice to reconfigure between any two given (connected) shapes. The worst-case number of sequential moves required to transform one connected configuration to another is known to be Theta(n). However, in principle, atoms can all move simultaneously. We develop a parallel algorithm for reconfiguration that runs in only O(log n) parallel steps, although the total number of operations increases slightly to Theta(nlogn). The result is the first (theoretically) almost-instantaneous universally reconfigurable robot built from simple units.},
  author = {G. Aloupis and S. Collette and E. D. Demaine and S. Langerman and V. Sacristan and S. Wuhrer},
  title = {Reconfiguration of {3D} Crystalline Robots Using {O}(log n) Parallel Moves},
  institution = {arXiv, Cornell University},
  number = {arXiv:0908.2440},
  year = {2009},
  pdf = {http://arxiv.org/abs/0908.2440},
  note = {21 pages}
}

@techreport{ACCLI09a,
  abstract = { 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 result depends on the
parameter alpha, which has been used to bound the maximum number of isosceles
triangles that can be formed by n points. This bound has been expressed as
O(n^{2+2alpha+epsilon}), and the current best value for alpha is ~0.068.
 Our algorithm finds polygons with O(n^alpha) edges by sweeping a line through
the set of points, while larger polygons are found by random sampling. We can
find all regular polygons with high probability in O(n^{2+alpha+epsilon})
expected time for every positive epsilon. This compares well to the
O(n^{2+2alpha+epsilon}) deterministic algorithm of Brass.},
  author = {G. Aloupis and J. Cardinal and S. Collette and J. Iacono and S. Langerman},
  title = {Detecting all regular polygons in a point set},
  institution = {arXiv, Cornell University},
  number = {arXiv:0908.2442},
  year = {2009},
  pdf = {http://arxiv.org/abs/0908.2442},
  note = {11 pages}
}

@techreport{ACCIKLSST09b,
  abstract = {Given a planar point set and an integer $k$, we wish to color the points with $k$ colors so that any axis-aligned strip containing enough points contains all colors. 
The goal is to bound the necessary size of such a strip, as a function of $k$. We show that if the strip size is at least $2k-1$, such a coloring can always be found. We prove that the size of the strip is also bounded in any fixed number of dimensions. 
In contrast to the planar case, we show that deciding whether a 3D point
set can be 2-colored so that any strip containing at least three
points contains both colors is NP-complete.

We also consider the problem of coloring a given set of axis-aligned strips, so that any sufficiently covered point in the plane is covered by $k$ colors. 
We show that in $d$ dimensions the required coverage is at most $d(k-1)+1$. 

Lower bounds are given for the two problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. Finally, we study a variant where strips are replaced by wedges. 
},
  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},
  institution = {arXiv, Cornell University},
  number = {arXiv:0904.2115},
  year = {2009},
  pdf = {http://arxiv.org/abs/0904.2115},
  note = {11 pages}
}

@techreport{ABBCDHKLPW09a,
  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},
  institution = {arXiv, Cornell University},
  number = {arXiv:0904.0262},
  year = {2009},
  pdf = {http://arxiv.org/abs/0904.0262},
  note = {14 pages}
}

@techreport{CDILM09a,
  author = {S. Collette and V. Dujmovi\'c and J. Iacono and S. Langerman and P. Morin},
  institution = {arXiv, Cornell University},
  number = {arXiv:0901.1908},
  title = {Entropy, Triangulation, and Point Location in Planar Subdivisions},
  year = {2009},
  pdf = {http://arxiv.org/abs/0901.1908},
  note = {19 pages}
}

@techreport{ACCLOR08b,
  abstract = {We prove that for every centrally symmetric convex polygon Q, there exists a constant alpha such that any alpha*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 Toth (SoCG'07). The question is motivated by a sensor network problem, in which a region has to be monitored by sensors with limited battery lifetime.},
  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},
  institution = {arXiv, Cornell University},
  number = {arXiv:0807.0552},
  year = {2008},
  pdf = {http://arxiv.org/abs/0807.0552},
  note = {14 pages}
}

@techreport{ACCHLOP08a,
  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},
  institution = {arXiv, Cornell University},
  number = {arXiv:0806.1416},
  year = {2008},
  pdf = {http://arxiv.org/abs/0806.1416},
  note = {18 pages}
}

@techreport{CCG08a,
  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},
  title = {Integrating Job Parallelism in Real-Time Scheduling Theory},
  institution = {arXiv, Cornell University},
  number = {arXiv:0805.3237},
  year = {2008},
  pdf = {http://arxiv.org/abs/0805.3237},
  note = {14 pages}
}

@techreport{ACCDDLOPT08,
  abstract = {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. The main focus of this work is a comparison of three alternate proofs, to show the links between Toponogov's Comparison Theorem, Legendre's Theorem and Cauchy's Arm Lemma.},
  author = {Z. Abel and D. Charlton and S. Collette and E. D. Demaine and M. L. Demaine and S. Langerman and J. O'Rourke and V. Pinciu and G. Toussaint},
  institution = {arXiv, Cornell University},
  number = {arXiv:0804.0986},
  title = {Cauchy's Arm Lemma on a Growing Sphere},
  year = {2008},
  pdf = {http://arxiv.org/abs/0804.0986},
  note = {10 pages}
}

@techreport{BCCS08,
  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},
  institution = {arXiv, Cornell University},
  number = {arXiv:0804.1041},
  title = {On the Stretch Factor of Convex Delaunay Graphs},
  year = {2008},
  pdf = {http://arxiv.org/abs/0804.1041},
  note = {16 pages}
}

@techreport{CCHLP07d,
  abstract = {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.},
  author = {J. Cardinal and S. Collette and F. Hurtado and S. Langerman and B. Palop},
  institution = {arXiv, Cornell University},
  number = {arXiv:0705.0635},
  title = {Moving Walkways, Escalators, and Elevators},
  year = {2007},
  pdf = {http://arxiv.org/abs/0705.0635},
  note = {16 pages}
}

@techreport{CILM06b,
  author = {S. Collette and J. Iacono and S. Langerman and P. Morin},
  institution = {Carleton University - School of Computer Science},
  number = {TR-06-13},
  title = {Distribution-Sensitive Point Location in Convex Subdivisions},
  year = {2006},
  pdf = {http://www.scs.carleton.ca/research/tech_reports/index.php?Abstract=2006/tr-06-13_0019},
  note = {15 pages}
}