Originators: Erik Demaine, Dion Harmon, John Iacono, Daniel Kane, and Mihai Pătraşcu (presented by K. J. Fox - REGS 2009)
Definitions: Given two points a and b in any point set P in Z², let [a,b] denote the axis aligned rectangle with corners a and b. We say a pair of points a and b in a point set P are arborally satisfied if a and b are in the same row or column, or if P-{a,b} has at least one point in [a,b]. Given an m×n grid and a point set X on the grid with exactly one point per row, we seek a smallest superset Y of X such that all pairs of points in Y are arborally satisfied (by Y). Let f(X) be the minimum number of points that must be added to X to obtain an arborally satisfied set Y.
Background: [DHIKM] showed that arborally satisfied point sets correspond to valid access sequences of nodes during the execution of a dynamic binary search tree algorithm that allows modifications to the tree structure. A point (si, i) in the given point set X represents a search request for node si at time i, and a point (x, i) in an arborally satisfied superset represents an access of node x during the search for si, assuming that each search begins from the root of the tree. A classical problem in data structures is to find a dynamically optimal binary search tree algorithm: an algorithm that accesses the minimum number of nodes required for any given search sequence, within constant factors.
Algorithm 1: (Demaine et al. [DHIKM]) Starting with point set X, sweep the grid using a horizontal line, iteratively increasing the height. At time i, the algorithm places the uniquely defined minimal set of points in row i that makes the point set from the bottom to row i arborally satisfied. Let g(X) be the number of points added by this algorithm.
Conjecture 1: (Demaine et al. [DHIKM]) g(X) = O(f(X)). More strongly, g(X) = f(X)+O(m).
Comments: Little was known about g(X) when [DHIKM] was written and submitted to conference. Iacono and Pătraşcu reportedly proved some theorems giving upper bounds on g(X) shortly thereafter. Erickson and Fox [2009] later proved similar (if not the same) theorems, including that g(X) = O(m lg n).
Algorithm 2+: (Demaine et al. [DHIKM]) Starting with point set X, sweep the grid using a horizontal line, iteratively increasing the height. At time i, the algorithm places the uniquely defined minimal set of points in row i to arborally satisfy all pairs of points a and b that form the bottom-left and upper-right corners of a rectangle with a in row i. Let g+(X) be the number of points added to point set X by this algorithm. Algorithm 2- and g-(X) are defined similarly, changing the sign of the slope of the line from b to a for the pairs to be satisfied.
Conjecture 2: (Erickson-Fox) g(X) ≤ g+(X)+g-(X).
Comments: We have used g(X),g+(X),g-(X) to indicate the greedy nature of these algorithms. Algorithms 2+ and 2- do not produce arborally satisfied sets, but Demaine et al. [DHIKM] proved that f(X) ≥ g+(X). Conjecture 2 would therefore imply g(X) ≤ 2 f(X). Consequently, the results of [DHIKM] could be used to find a dynamically optimal binary search tree algorithm.
Partial Solution: Fox, Orlow, and Vanderzee (REGS 2009) found a counterexample to Conjecture 2. However, if g(X) is bounded by some multiple of g+(X)+g-(X), then still there would be a positive result toward Conjecture 1.
References:
[DHIKM] Demaine, E.; Harmon, D.; Iacono, J.; Kane, D.; Pătraşcu, M.
The geometry of binary search trees. In Proc. 20th ACM/SIAM Symposium on Discrete Algorithms (SODA),
pp. 496-505, 2009.