Search

We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval $I$ there is a color that appears exactly once in $I$. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number $n$ of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring $\Omega(\sqrt{n})$ colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses $O(\log^2 n)$ colors, and the second is randomized and uses $O(\log n)$ colors with high probability. We also show that the $O(\log^2 n)$ bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only $O(\log n)$ colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, $n$ colors may be required in the worst case.

We show that a set of $n$ points in the plane has at most $O(10.05^n)$ perfect matchings with crossing-free straight-line embedding. The expected number of perfect crossing-free matchings of a set of $n$ points drawn independently and identically distributed from an arbitrary distribution in the plane is at most $O(9.24^n)$. Several related bounds are derived: (a) The number of all (not necessarily perfect) crossing-free matchings is at most $O(10.43^n)$. (b) The number of red-blue perfect crossing-free matchings (where the points are colored red or blue and each edge of the matching must connect a red point with a blue point) is at most $O(7.61^n)$. (c) The number of left-right perfect crossing-free matchings (where the points are designated as left or right endpoints of the matching edges) is at most $O(5.38^n)$. (d) The number of perfect crossing-free matchings across a line (where all the matching edges must cross a fixed halving line of the set) is at most $4^n$. These bounds are employed to infer that a set of $n$ points in the plane has at most $O(86.81^n)$ crossing-free spanning cycles (simple polygonizations) and at most $O(12.24^n)$ crossing-free partitions (these are partitions of the point set so that the convex hulls of the individual parts are pairwise disjoint). We also derive lower bounds for some of these quantities.

This paper presents the problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that $\Omega (\frac{1}{{d^2 }}) \leqslant R \leqslant \frac{{2\pi }}{d}$ for any graph. Moreover, it is proved that $R = \Theta (\frac{1}{d})$ for many graphs including planar graphs, complete graphs, hypercubes, multidimensional meshes and tori, and other special networks. It is also shown that the problem of deciding if $R = \frac{{2\pi }}{d}$ for a graph is NP-hard for $d = 4$, and by using a counting argument that $R = O(\frac{{\log d}}{{d^2 }})$ for many graphs.

For H a set of lines in the Euclidean plane, $A(H)$ denotes the induced dissection, called the arrangement of H. We define the notion of a belt in $A(H)$, which is bounded by a subset of the edges in $A(H)$, and describe two algorithms for constructing belts. All this is motivated by applications to a host of seemingly unrelated problems including a type of range search and finding the minimum area triangle with the vertices taken from some finite set of points.