Authors Parinya Chalermsook, Julia Chuzhoy, Thatchaphol Saranurak,
License CC-BY-3.0
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71
www.theoryofcomputing.org
S PECIAL ISSUE : APPROX-RANDOM 2020
Pinning Down the Strong Wilber-1 Bound
for Binary Search Trees
Parinya Chalermsookโก Julia Chuzhoyยง Thatchaphol Saranurak
Received June 13, 2021; Revised August 10, 2022; Published December 19, 2023
Abstract. Dynamic Optimality Conjecture, postulating the existence of an ๐(1)-
competitive online algorithm for binary search trees (BSTs), is among the most
fundamental open problems in dynamic data structures. The conjecture remains
wide open, despite extensive work and some notable progress, including, for
example, the ๐(log log ๐)-competitive Tango Trees, which is the best currently
known competitive ratio. One of the main hurdles towards settling the conjecture is
that we currently do not have polynomial-time approximation algorithms achieving
better than an ๐(log log ๐)-approximation, even in the offline setting. All known
non-trivial algorithms for BSTs rely on comparing the algorithmโs cost with the
so-called Wilber-1 bound (WB-1). Therefore, establishing the worst-case relationship
An extended abstract of this paper appeared in the Proceedings of the 23rd Internat. Conf. on Approximation
Algorithms and Combinatorial Optimization (APPROXโ20)
โก Supported by the European Research Council (ERC) under the European Unionโs Horizon 2020 research and
innovation programme (grant agreement No. 759557) and by the Academy of Finland Research Fellows program,
under grant No. 310415.
ยง Supported in part by NSF grant CCF-1616584. Part of the work was done while the second author was a Weston
visiting professor at the Department of Computer Science and Applied Mathematics, Weizmann Institute of Science.
ACM Classification: Theory of computation โ Data structure design and analysis
AMS Classification: 68Q25, 68W25
Key words and phrases: binary search trees, dynamic optimality, data structures
ยฉ 2023 Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak
c b Licensed under a Creative Commons Attribution License (CC-BY) DOI: 10.4086/toc.2023.v019a008
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
between this bound and the optimal solution cost appears crucial for further progress,
and it is an interesting open question in its own right.
Our contribution is twofold. First, we show that the gap between WB-1 and
the optimal solution value can be as large as ฮฉ(log log ๐/log log log ๐); in fact, we
show that the gap holds even for several stronger variants of the bound.1 Second,
we show,
given an integer
๐ท > 0, a ๐ท-approximation algorithm that runs in time
ฮฉ(๐ท)
exp ๐ ๐ 1/2 log ๐ . In particular, this yields a constant-factor approximation
algorithm with subexponential running time.2 Moreover, we obtain a simpler and
cleaner efficient ๐(log log ๐)-approximation algorithm that can be used in an online
setting. Finally, we suggest a new bound, that we call the Guillotine Bound, that is
stronger than WB-1, while maintaining its algorithm-friendly nature, that we hope
will lead to better algorithms. All our results use the geometric interpretation of the
problem, leading to cleaner and simpler analysis.
1 Introduction
1.1 Binary search trees
Binary search trees (BSTโs) are a fundamental data structure that has been extensively studied
for many decades. Informally, suppose we are given as input an online access sequence
๐ = {๐ฅ 1 , . . . , ๐ฅ ๐ } of keys from {1, . . . , ๐}, and our goal is to maintain a binary search tree ๐
over the set {1, . . . , ๐} of keys. The algorithm is allowed to modify the tree ๐ after each access;
the tree obtained after the ๐th access is denoted by ๐๐+1 . Each such modification involves a
sequence of rotation operations that transform the current tree ๐๐ into a new tree ๐๐+1 . The cost
of the transformation is the total number of rotations performed plus the depth of the key ๐ฅ ๐
in the tree ๐๐ . The total cost of the algorithm is the total cost of all transformations performed
as the sequence ๐ is processed. We denote by OPT(๐) the smallest cost of any algorithm for
maintaining a BST for the access sequence ๐, when the whole sequence ๐ is known to the
algorithm in advance.
Several algorithms for BSTโs, whose costs are guaranteed to be ๐(๐ log ๐) for any access
sequence, such as AVL-trees [1] and red-black trees [2], are known since the 60โs (see [10],
Chapters 12 and 13). Moreover, it is well known that there are length-๐ access sequences ๐
on ๐ keys, for which OPT(๐) = ฮฉ(๐ log ๐). However, such optimal worst-case guarantees are
often unsatisfactory from both practical and theoretical perspectives, as one can often obtain
better results for โstructuredโ inputs. Arguably, a better notion of the algorithmโs performance
to consider is instance optimality, where the algorithmโs performance is compared to the optimal
cost OPT(๐) for the specific input access sequence ๐. This notion is naturally captured by the
algorithmโs competitive ratio: we say that an algorithm for BSTโs is ๐ผ-competitive, if, for every
1A recent independent paper by Lecomte and Weinstein (ESAโ20) shows an even stronger, ฮฉ(log log ๐), separation.
2The term โsubexponential timeโ in this paper refers to the running time 2๐(๐) .
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 2
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
online input access sequence ๐, the cost of the algorithmโs execution on ๐ is at most ๐ผ ยท OPT(๐).
Since for every length-๐ access sequence ๐, OPT(๐) โฅ ๐, the above-mentioned algorithms
that provide worst-case ๐(๐ log ๐)-cost guarantees are also ๐(log ๐)-competitive. However,
there are many known important special cases, in which the value of the optimal solution is
๐(๐), and for which the existence of an ๐(1)-competitive algorithm would lead to a much
better performance, including some interesting applications, such as, for example, adaptive
sorting [27, 7, 23, 26, 15, 24, 13, 9, 8, 3, 6, 5, 19].
1.1.1 The Dynamic Optimality Conjecture
A striking conjecture of Sleator and Tarjan [25] from 1985, called the dynamic optimality conjecture,
asserts that the Splay Trees provide an ๐(1)-competitive algorithm for BSTโs. This conjecture has
sparked a long line of research, but despite the continuing effort, and the seeming simplicity
of BSTโs, it remains widely open. In a breakthrough result, Demaine et al. [12] proposed the
Tango Trees algorithm, that achieves an ๐(log log ๐)-competitive ratio, and has remained the
best known algorithm for the problem, for over 15 years. A natural avenue for overcoming this
barrier is to first consider the โeasierโ task of designing (offline) approximation algorithms,
whose approximation factor is below ๐(log log ๐). Designing better approximation algorithms
is often a precursor to obtaining better online algorithms, and it is a natural stepping stone
towards this goal.
1.1.2 The Wilber bounds
The main obstacle towards designing better algorithms, both in the online and the offline settings,
is obtaining tight lower bounds on the value OPT(๐), that can be used in algorithm design. In
order to improve upon the trivial ๐(log ๐) approximation, the lower bound OPT(๐) โฅ ๐ is not
sufficient1. Wilber [29] proposed two new bounds, that we refer to as the Wilber-1 Bound, or
Wilberโs first bound, (WB-1) and the Wilber-2 Bound (WB-2). He proved that, for every input
sequence ๐, the values of both these bounds on ๐ are at most OPT(๐). The breakthrough
result of Demaine et al. [12], that gives an ๐(log log ๐)-competitive online algorithm, relies
on the WB-1 bound. In particular, they show that the cost of the solution produced by their
algorithm is within an ๐(log log ๐)-factor from the WB-1 bound on the given input sequence ๐,
and hence from OPT(๐). This in turn implies that, for every input sequence ๐, the value of the
WB-1 bound is within an ๐(log log ๐) factor from OPT(๐). Follow-up work [28, 16] improved
several aspects of Tango Trees, but it did not improve the approximation factor. Additional
lower bounds on OPT, that subsume both the WB-1 and the WB-2 bounds, were suggested in
[11, 14, 17], but unfortunately it is not clear how to exploit them in algorithm design. To this day,
the only method we have for designing non-trivial online or offline approximation algorithms
for BSTโs is by relying on the WB-1 bound, and this seems to be the most promising approach
for obtaining better algorithms. In order to make further progress on both online and offline
1This is due to the existence of sequences ๐ with OPT(๐) = ฮฉ(๐ log ๐).
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 3
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
approximation algorithms for BSTโs, it therefore appears crucial that we better understand the
relationship between the WB-1 bound and the optimal solution cost.
Informally, the WB-1 bound relies on recursive partitioning of the input key sequence, that can be
represented by a partitioning tree. The standard WB-1 bound (that we refer to as the weak WB-1
bound) only considers a single such partitioning tree. It is well-known (see, e.g., [12, 28, 18]),
that the gap between OPT(๐) and the weak WB-1 bound for an access sequence ๐ may be as
large as ฮฉ(log log ๐). However, the โbadโ access sequence ๐ used to obtain this gap is highly
dependent on the fixed partitioning tree ๐. It is then natural to consider a stronger variant of
WB-1, that we refer to as strong WB-1 bound and denote by WB(๐), that maximizes the weak
WB-1 bound over all such partitioning trees. As suggested by Iacono [18], and by Kozma [20],
this gives a promising approach for improving the ๐(log log ๐)-approximation factor.
1.1.3 Our results
In this paper, we show that, even for this strong variant of WB-1, the gap between OPT(๐) and
WB(๐) may be as large as ฮฉ(log log ๐/log log log ๐). This negative result extends to an even
stronger variant of WB-1 that we discuss below.
Our second set of results is algorithmic. We show, for any positive integer
๐ท, an (offline) ๐ท-
ฮฉ(๐ท)
approximation algorithm that runs in time poly(๐) ยท exp ๐(๐ 1/2 log ๐) . When ๐ท is constant,
we obtain an ๐(1)-approximation in subexponential time. When ๐ท is ฮ(log log ๐), our algorithm
matches current polynomial-time approximation ratio, which is ๐(log log ๐). In the latter case,
we can also adapt the algorithm to the online setting, obtaining an ๐(log log ๐)-competitive
online algorithm.
All our results use the geometric interpretation of the problem, introduced by Demaine et al. [11],
leading to clean divide-and-conquer-style arguments that avoid, for example, the notion of
pointers and rotations. We feel that this approach, in addition to providing a cleaner and simpler
view of the problem, is more natural to work with in the context of approximation algorithms,
and should be more amenable to the powerful geometric techniques in the field.
1.2 Independent work
Independently from our work, Lecomte and Weinstein [21] showed that second Wilber bound
(also called funnel bound) dominates WB-1, and moreover, they show an access sequence ๐ for
which the two bounds have a gap of ฮฉ(log log ๐). In particular, their result implies that the gap
between WB(๐) and OPT(๐) is ฮฉ(log log ๐) for that access sequence. Their result subsumes our
Theorem 1.1 entirely (but not the extension discussed in Section 1.3.3).
We note that the access sequence ๐ used in our negative results provides a gap of
ฮฉ(log log ๐/log log log ๐)
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 4
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
between the WB-2 and the WB-1 bounds, although we only realized this after hearing the
statement of the results of [21]. Additionally, Lecomte and Weinstein show that WB-2 is invariant
under rotations, and use this to show that, when the WB-2 is constant, then the Independent
Rectangle bound of [11] is linear.
1.3 Statements of our results
We now formally state our results.
1.3.1 Geometric representation
We use the geometric interpretation of the problem, introduced by Demaine et al. [11], that we
refer to as the Min-Sat problem. Let ๐ be any set of points in the plane. We say that two points
๐, ๐ โ ๐ are aligned iff either their ๐ฅ-coordinates are equal, or their ๐ฆ-coordinates are equal. If ๐
and ๐ are not aligned, then let ๐,๐ be the smallest closed axis-aligned rectangle containing both
๐ and ๐; notice that ๐ and ๐ must be diagonally opposite corners of this rectangle. We say that
the pair (๐, ๐) of points is satisfied in ๐ iff there is some additional point ๐ โ ๐, ๐ in ๐ that lies in
๐,๐ (the point may lie on the boundary of the rectangle). Lastly, we say that the set ๐ of points
is satisfied iff for every pair ๐, ๐ โ ๐ of distinct points, either ๐ and ๐ are aligned, or they are
satisfied in ๐.
In the Min-Sat problem, the input is a set ๐ of points in the plane with integral ๐ฅ- and ๐ฆ-
coordinates; we assume that all ๐ฅ-coordinates are between 1 and ๐, and all ๐ฆ-coordinates
are between 1 and ๐ and distinct from each other, and that |๐| = ๐. The goal is to find a
minimum-cardinality set ๐ of points, such that the set ๐ โช ๐ of points is satisfied.
An access sequence ๐ over keys {1, . . . , ๐} can be represented by a set ๐ of points in the plane
as follows: if a key ๐ฅ is accessed at time ๐ฆ, then add the point (๐ฅ, ๐ฆ) to ๐. Demaine et al. [11]
showed that, for every access sequence ๐, if we denote by ๐ the corresponding set of points in
the plane, then the value of the optimal solution to the Min-Sat problem on ๐ is ฮ(OPT(๐)). They
also showed that, in order to obtain an ๐(๐ผ)-approximation algorithm for BSTโs, it is sufficient
to obtain an ๐ผ-approximation algorithm for the Min-Sat problem. In the online version of the
Min-Sat problem, at every time step ๐ก, we discover the unique input point whose ๐ฆ-coordinate is
๐ก, and we need to make an irrevocable decision on which points with ๐ฆ-coordinate ๐ก to add to
the solution. Demaine et al. [11] also showed that an ๐ผ-competitive online algorithm for Min-Sat
implies an ๐(๐ผ)-competitive online algorithm for BSTโs. For convenience, we do not distinguish
between the input access sequence ๐ and the corresponding set of points in the plane, that we
also denote by ๐.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 5
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
1.3.2 Negative results for WB-1
We say that an input access sequence ๐ is a permutation if each key in {1, . . . , ๐} is accessed
exactly once. Equivalently, in the geometric view, every column with an integral ๐ฅ-coordinate
contains exactly one input point.
Informally, the WB-1 bound for an input sequence ๐ is defined as follows. Let ๐ต be the bounding
box containing all points of ๐, and consider any vertical line ๐ฟ drawn across ๐ต, that partitions
it into two vertical strips, separating the points of ๐ into two subsets ๐1 and ๐2 . Assume
that the points of ๐ are ordered by their ๐ฆ-coordinates from smallest to largest. We say that
a pair (๐ฅ, ๐ฅ 0) โ ๐ of points cross the line ๐ฟ, iff ๐ฅ and ๐ฅ 0 are consecutive points of ๐, and they
lie on different sides of ๐ฟ. Let ๐ถ(๐ฟ) be the number of all pairs of points in ๐ that cross ๐ฟ.
We then continue this process recursively with ๐1 and ๐2 , with the final value of the WB-1
bound being the sum of the two resulting bounds obtained for ๐1 and ๐2 , and ๐ถ(๐ฟ). This
recursive partitioning process can be represented by a binary tree ๐ that we call a partitioning
tree (we note that the partitioning tree is not related to the BST tree that the BST algorithm
maintains). Every vertex ๐ฃ of the partitioning tree is associated with a vertical strip ๐(๐ฃ),
where for the root vertex ๐, ๐(๐) = ๐ต. If the partitioning algorithm uses a vertical line ๐ฟ to
partition the strip ๐(๐ฃ) into two sub-strips ๐1 and ๐2 , then vertex ๐ฃ has two children, whose
corresponding strips are ๐1 and ๐2 . Note that every sequence of vertical lines used in the
recursive partitioning procedure corresponds to a unique partitioning tree and vice versa. Given
a set ๐ of points and a partitioning tree ๐, we denote by WB๐ (๐) the WB-1 bound obtained for
๐ while following the partitioning scheme defined by ๐. Wilber [29] showed that, for every
partitioning tree ๐, OPT(๐) โฅ ฮฉ(WB๐ (๐)) holds. Moreover, Demaine et al. [12] showed that, if
๐ is a balanced tree, then OPT(๐) โค ๐(log log ๐) ยท WB๐ (๐). These two bounds are used to obtain
the ๐(log log ๐)-competitive algorithm of [12]. We call this variant of WB-1, that is defined with
respect to a fixed tree ๐, the weak WB-1 bound.
Unfortunately, it is well-known (see, e.g., [12, 28, 18]), that the gap between OPT(๐) and
the weak WB-1 bound on an input ๐ may be as large as ฮฉ(log log ๐). In other words, for
any fixed partitioning tree ๐, there exists an input ๐ (that depends on ๐), with WB๐ (๐) โค
๐(OPT(๐)/log log ๐). However, the construction of this โbadโ input ๐ depends on the fixed
partitioning tree ๐.
We consider a stronger variant of WB-1, that we refer to as strong WB-1 bound and denote
by WB(๐), that maximizes the weak WB-1 bound over all such partitioning trees, that is,
WB(๐) = max๐ {WB๐ (๐)}.
Using this stronger bound as an alternative to weak WB-1 in order to obtain better approximation
algorithms was suggested by Iacono [18], and by Kozma [20].
Our first result rules out this approach: we show that, even for the strong WB-1 bound, the gap
between WB(๐) and OPT(๐) may be as large as ฮฉ(log log ๐/log log log ๐), even if the input ๐ is
a permutation.
Theorem 1.1. For infinitely many integer ๐, there exists an access sequence ๐ on ๐ keys with |๐ | = ๐,
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 6
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
such that ๐ is a permutation, OPT(๐) โฅ ฮฉ(๐ log log ๐), but WB(๐) โค ๐(๐ log log log ๐).
log log ๐
In particular, for every partitioning tree ๐, OPT (๐)
WB (๐)
โฅฮฉ log log log ๐ for infinitely many sequences
๐
๐. We note that it is well known (see, e.g., [6]), that any ๐-approximation algorithm for
permutation input can be turned into an ๐(๐)-approximation algorithm for any input sequence.
However, the known instances that achieve an ฮฉ(log log ๐)-gap between the weak WB-1 bound
and OPT are not permutations. Therefore, our result is the first to provide a super-constant gap
between WB-1 and OPT for permutations, even for the case of weak WB-1.
1.3.3 Extension of WB-1
We consider natural generalizations of the WB-1 bound that allow partitioning the plane both
horizontally and vertically. We call the new bounds the consistent Guillotine Bound and the
Guillotine Bound. Our negative result extends to the consistent Guillotine Bound but not to the
Guillotine Bound. The Guillotine Bound seems to maintain the algorithm-friendly nature of
WB-1, and in particular it naturally fits into the algorithmic framework that we propose. We
hope that this bound can lead to improved algorithms, both in the offline and the online settings
1.3.4 Separating the two Wilber bounds
The sequence ๐ given by Theorem 1.1 not only provides a separation between WB-1 and OPT,
but it also provides a separation between WB-1 and WB-2. The latter can be defined in the
geometric view as follows. Recall that, for a pair of points ๐ฅ, ๐ฆ โ ๐, ๐ฅ,๐ฆ is the smallest closed
rectangle containing both ๐ฅ and ๐ฆ. For a point ๐ฅ in the access sequence ๐, the funnel of ๐ฅ is
the set of all points ๐ฆ โ ๐, for which ๐ฅ,๐ฆ does not contain any point of ๐ \ {๐ฅ, ๐ฆ}, and alt(๐ฅ)
is the number of alterations between the left of ๐ฅ and the right of ๐ฅ in the funnel of ๐ฅ. The
second Wilber Bound for sequence ๐ is then defined as: WB(2) (๐) = |๐ | + ๐ฅโ๐ alt(๐ฅ). We
ร
show that, for the sequence ๐ given by Theorem 1.1, WB(2) (๐) โฅ ฮฉ(๐ log log ๐) holds, and
therefore WB(2) (๐)/WB(๐) โฅ ฮฉ(log log ๐/log log log ๐) for that sequence, implying that the gap
between WB(๐) and WB(2) (๐) may be as large as ฮฉ(log log ๐/log log log ๐). We note that we only
realized that our results provide this stronger separation between the two Wilber bounds after
hearing the statements of the results from the independent work of Lecomte and Weinstein [21]
mentioned above.
1.3.5 Algorithmic results
We provide new simple approximation algorithms for the problem, that rely on its geometric
interpretation, namely the Min-Sat problem.
Theorem 1.2. There is an offline algorithm for Min-Sat, that, given any integer ๐ท โฅ 1, and an access
sequence ๐ of length m to n keys, produces a solution of cost at most ๐ท ยท OPT(๐) and has running time
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 7
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
ฮฉ(๐ท)
poly(๐) ยท exp ๐ ๐ 1/2 log ๐ . For ๐ท = ฮ(log log ๐), the algorithmโs running time is polynomial
in ๐ and ๐, and it can be adapted to the online setting, achieving an ๐(log log ๐)-competitive ratio.
While the ๐(log log ๐)-approximation factor achieved by our algorithm in time poly(๐๐) is
similar to that achieved by other known algorithms [12, 16, 28], this is the first algorithm that
relies solely on the geometric formulation of the problem, which is arguably cleaner, simpler,
and better suited for exploiting the rich toolkit of algorithmic techniques developed in the areas
of online and approximation algorithms.
1.3.6 Erratum
Some erroneous complexity theoretic inferences, made in the paragraph following the statement
of Theorem 2 (page 33:6) in the conference version of this paper [4], are retracted in the
present article. In particular, at this time we are unable to rule out, under any plausible
complexity-theoretic assumption, the possibility that constant-factor approximation of Min-Sat
is NP-hard.
The main results are not affected and are identical in the two versions.
2 Preliminaries
All our results only use the geometric interpretation of the problem, that we refer to as the
Min-Sat problem. We include the formal definition of algorithms for BSTโs and formally state
their equivalence.
2.1 The Min-Sat problem
For a point ๐ โ โ2 in the plane, we denote by ๐.๐ฅ and ๐.๐ฆ its ๐ฅ- and ๐ฆ-coordinates, respectively.
Given any pair ๐, ๐ 0 of points, we say that they are aligned if ๐.๐ฅ = ๐ 0 .๐ฅ or ๐.๐ฆ = ๐ 0 .๐ฆ. If ๐ and ๐ 0
are not aligned, then we let ๐,๐0 be the smallest closed axis-aligned rectangle containing both ๐
and ๐ 0; note that ๐ and ๐ 0 must be diagonally opposite corners of the rectangle.
Definition 2.1. We say that a non-aligned pair ๐, ๐ 0 of points is satisfied by a point ๐ 00 if ๐ 00 is
distinct from ๐ and ๐ 0 and ๐ 00 โ ๐,๐0 (where ๐ 00 may lie on the boundary of the rectangle). We
say that a set ๐ of points is satisfied if for every non-aligned pair ๐, ๐ 0 โ ๐ of points, there is some
point ๐ 00 โ ๐ that satisfies this pair.
We refer to horizontal and vertical lines as rows and columns respectively. For a collection of
points ๐, the active rows of ๐ are the rows that contain at least one point in ๐. We define the
notion of active columns analogously. We denote by ๐(๐) and ๐(๐) the number of active rows and
active columns of the point set ๐, respectively. We say that a point set ๐ is a semi-permutation
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 8
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
if every active row contains exactly one point of ๐. Note that, if ๐ is a semi-permutation,
then ๐(๐) โค ๐(๐). We say that ๐ is a permutation if it is a semi-permutation, and additionally,
every active column contains exactly one point of ๐. Clearly, if ๐ is a permutation, then
๐(๐) = ๐(๐) = |๐ |. We denote by ๐ต the smallest closed rectangle containing all points of ๐, and
call ๐ต the bounding box.
We are now ready to define the Min-Sat problem. The input to the problem is a set ๐ of points
that is a semi-permutation, and the goal is to compute a minimum-cardinality set ๐ of points,
such that ๐ โช ๐ is satisfied. We say that a set ๐ of points is a feasible solution for ๐ if ๐ โช ๐ is
satisfied. We denote by OPT(๐) the minimum value |๐| of any feasible solution ๐ for ๐.2
In the online version of the Min-Sat problem, at every time step ๐ก, we discover the unique input
point from ๐ whose ๐ฆ-coordinate is ๐ก, and we need to make an irrevocable decision on which
points with ๐ฆ-coordinate ๐ก to add to the solution ๐. As shown by Demaine et al. [11], the Min-Sat
problem is equivalent to the BST problem, in the following sense:
Theorem 2.2 (Demaine et al.). Any efficient ๐ผ-approximation algorithm for Min-Sat can be transformed
into an efficient ๐(๐ผ)-approximation algorithm for BSTโs, and similarly any online ๐ผ-competitive
algorithm for Min-Sat can be transformed into an online ๐(๐ผ)-competitive algorithm for BSTโs.
2.2 Basic geometric properties
The following observation is well known (see, e.g., Observation 2.1 from [11]).
Observation 2.3. Let ๐ be any satisfied point set. Then for every pair ๐, ๐ โ ๐ of distinct points,
there is a point ๐ โ ๐,๐ \ {๐, ๐} such that ๐.๐ฅ = ๐.๐ฅ or ๐.๐ฆ = ๐.๐ฆ.
Proof. Since the set ๐ is satisfied, rectangle ๐,๐ must contain at least one point of ๐ that is
distinct from ๐ and ๐. Among all such points, let ๐ be the one with smallest โ1 -distance to ๐.
We claim that either ๐.๐ฅ = ๐.๐ฅ, or ๐.๐ฆ = ๐.๐ฆ. Indeed, assume otherwise. Then ๐ and ๐ are not
aligned, but no point of ๐ lies in ๐,๐ \ {๐, ๐}, contradicting the fact that ๐ is a satisfied point
set.
2.2.1 Collapsing sets of columns or rows
Assume that we are given any set ๐ of points, and any collection ๐ of consecutive active columns
for ๐. In order to collapse the set ๐ of columns, we replace ๐ with a single representative
column ๐ถ (for concreteness, we use the column of ๐ with minimum ๐ฅ-coordinate). For every
point ๐ โ ๐ that lies on a column of ๐, we replace ๐ with a new point, lying on the column ๐ถ,
whose ๐ฆ-coordinate remains the same. Formally, we replace point ๐ with point (๐ฅ, ๐.๐ฆ), where
2In the original paper that introduced this problem [11], the value of the solution is defined as |๐ โช ๐|, while
our solution value is |๐|. For the purpose of showing the results in this paper, the two definitions are equivalent to
within a factor of 2.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 9
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
๐ฅ is the ๐ฅ-coordinate of the column ๐ถ. We denote by ๐|๐ the resulting new set of points. We can
similarly define collapsing set of rows. The following useful observation is easy to verify.
Observation 2.4. Let ๐ be any set of points, and let ๐ be any collection of consecutive active
columns (or rows) with respect to ๐. If ๐ is a satisfied set of points, then so is ๐ |๐ .
Proof. It is sufficient to prove the observation for the case where ๐ contains two consecutive
active columns, that we denote by ๐ถ and ๐ถ 0, which are collapsed into the column ๐ถ. We can
then apply this argument iteratively to collapse any number of columns.
Assume for contradiction that the set ๐ |๐ of points is not satisfied, and let ๐, ๐ โ ๐ |๐ be a pair
of points that are not satisfied. Note that, if ๐ and ๐ cannot both lie on the column ๐ถ in ๐ |๐ .
Moreover, if both ๐ and ๐ lie to the right, or to the left of the column ๐ถ, then they continue to be
satisfied by the same point ๐ โ ๐ that satisfied them in set ๐. We now consider two cases.
Assume first that ๐ lies to the left of the column ๐ถ, and ๐ lies to the right of the column ๐ถ in
point set ๐ |๐ . Let ๐ be the point that satisfied the pair (๐, ๐) in point set ๐. If ๐ lied on column ๐ถ
in ๐, then it remains on column ๐ถ in ๐ |๐ . If ๐ lied on column ๐ถ 0 in ๐, then a copy of ๐ lies on
column ๐ถ in ๐ |๐ , and this copy continues to satisfy the pair (๐, ๐). Otherwise, point ๐ belongs to
set ๐ |๐ , and it continues to satisfy the pair (๐, ๐).
It now remains to consider the case when exactly one of the two points (say ๐) lies on the column
๐ถ in ๐ |๐ . Assume w.l.o.g. that ๐ lies to the right of ๐ and below it in ๐ |๐ . Then either ๐ belongs
to ๐ (in which case we denote ๐ 0 = ๐), or ๐ is a copy of some point ๐ 0 that lies on column ๐ถ 0 in
๐. Let ๐ be the point that satisfies the pair (๐ 0 , ๐) of points in ๐. Using the same reasoning as
before, it is easy to see that either ๐ belongs to ๐ |๐ , where it continues to satisfy the pair (๐, ๐) of
points, or a copy of ๐ belongs to ๐ |๐ , and it also continues to satisfy the pair (๐, ๐).
It is easy to verify that an analogue of Observation 2.4 holds for collapsing rows as well.
2.2.2 Canonical solutions
We say that a solution ๐ for input ๐ is canonical iff every point ๐ โ ๐ lies on an active row and
an active column of ๐. It is easy to see that any solution can be transformed into a canonical
solution, without increasing its cost.
Observation 2.5. There is an efficient algorithm, that, given an instance ๐ of Min-Sat and any
feasible solution ๐ for ๐, computes a feasible canonical solution ๐ห for ๐ with |๐|
ห โค |๐|.
Proof. Let ๐ถ and ๐ถ 0 be any pair of consecutive active columns for ๐, such that some point of
๐ lies strictly between ๐ถ and ๐ถ 0. Let ๐ be the set of all columns that lie between ๐ถ and ๐ถ 0,
including ๐ถ but excluding ๐ถ 0, that contain points of ๐ โช ๐. We collapse the columns in ๐ into
the column ๐ถ, obtaining a new feasible solution for instance ๐ (we use Observation 2.4). We
continue this process until every point of the resulting solution ๐ lies on an active column, and
we perform the same procedure for the rows.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 10
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
2.3 Partitioning trees
We now turn to define partitioning trees, that are central to both defining the WB-1 bound and
to describing our algorithm.
Let ๐ be the a set of points that is a semi-permutation. We can assume without loss of generality
that every column with an integral ๐ฅ-coordinate between 1 and ๐(๐) inclusive contains at least
one point of ๐. Let ๐ต be the bounding box of ๐. Assume that the set of active columns is
{๐ถ1 , . . . , ๐ถ ๐ }, where ๐ = ๐(๐), and that for all 1 โค ๐ โค ๐, the ๐ฅ-coordinate of column ๐ถ ๐ is ๐. Let
โ be the set of all vertical lines with half-integral ๐ฅ-coordinates between 1 + 1/2 and ๐ โ 1/2
(inclusive). Throughout, we refer to the vertical lines in โ as auxiliary columns. Let ๐ be an
arbitrary ordering of the lines of โ and denote ๐ = (๐ฟ1 , ๐ฟ2 , . . . , ๐ฟ ๐โ1 ). We define a hierarchical
partition of the bounding box ๐ต into vertical strips using ๐, as follows. We perform ๐ โ 1
iterations. In the first iteration, we partition the bounding box ๐ต, using the line ๐ฟ1 , into two
vertical strips, ๐๐ฟ and ๐๐ต . For 1 < ๐ โค ๐ โ 1, in iteration ๐ we consider the line ๐ฟ ๐ , and we let ๐ be
the unique vertical strip in the current partition that contains the line ๐ฟ ๐ . We then partition ๐
into two vertical sub-strips by the line ๐ฟ ๐ . When the partitioning algorithm terminates, every
vertical strip contains exactly one active column.
Figure 1: An Illustration of a partitioning tree and the corresponding sequence ๐ = (๐ฟ1 , . . . , ๐ฟ7 ).
Strip ๐(๐ฃ) corresponds to node ๐ฃ that owns line ๐ฟ6 .
This partitioning process can be naturally described by a binary tree ๐ = ๐(๐), that we call a
partitioning tree associated with the ordering ๐ (see Figure 1). Each node ๐ฃ โ ๐(๐) is associated
with a vertical strip ๐(๐ฃ) of the bounding box ๐ต. The strip ๐(๐) of the root vertex ๐ of ๐ is the
bounding box ๐ต. For every inner vertex ๐ฃ โ ๐(๐), if ๐ = ๐(๐ฃ) is the vertical strip associated with
๐ฃ, and if ๐ฟ โ โ is the first line in ๐ that lies strictly in ๐, then line ๐ฟ partitions ๐ into two sub-strips,
๐(๐ฃ1 ) and ๐(๐ฃ2 ), corresponding to the two children ๐ฃ 1 and ๐ฃ 2 of ๐ฃ in the partitioning tree. We
say that ๐ฃ owns the line ๐ฟ, and we denote ๐ฟ = ๐ฟ(๐ฃ). For each leaf node ๐ฃ, the corresponding strip
๐(๐ฃ) contains exactly one active column of ๐, and ๐ฃ does not own any line of โ. For each vertex
๐ฃ โ ๐(๐), let ๐(๐ฃ) = |๐ โฉ ๐(๐ฃ)| be the number of points from ๐ that lie in ๐(๐ฃ), and let width(๐ฃ)
be the width of the strip ๐(๐ฃ). Given a partition tree ๐ for point set ๐, we refer to the vertical
strips in {๐(๐ฃ)} ๐ฃโ๐ as ๐-strips.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 11
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
2.4 The WB-1 bound
The WB-1 bound3 is defined with respect to an ordering (or a permutation) ๐ of the auxiliary
columns, or, equivalently, with respect to the partitioning tree ๐(๐). It will be helpful to keep
both these views in mind. In this paper, we will make a clear distinction between a weak variant
of the WB-1 bound, as defined by Wilber himself in [29] and a strong variant, as mentioned in
[18].
Let ๐ be a semi-permutation, and let โ be the corresponding set of auxiliary columns. Consider
an arbitrary fixed ordering ๐ of columns in โ and its corresponding partition tree ๐ = ๐(๐). For
each inner node ๐ฃ โ ๐(๐), consider the set ๐ 0 = ๐ โฉ ๐(๐ฃ) of input points that lie in the strip ๐(๐ฃ),
and let ๐ฟ(๐ฃ) โ โ be the line that ๐ฃ owns. We denote ๐ 0 = {๐ 1 , ๐2 , . . . , ๐ ๐ }, where the points
are indexed in the increasing order of their ๐ฆ-coordinates; since ๐ is a semi-permutation, no
two points of ๐ may have the same ๐ฆ-coordinate. For 1 โค ๐ < ๐, we say that the ordered pair
(๐ ๐ , ๐ ๐+1 ) of points form a crossing of ๐ฟ(๐ฃ) iff ๐ ๐ , ๐ ๐+1 lie on the opposite sides of the line ๐ฟ(๐ฃ). We
let cost(๐ฃ) be the total number of crossings of ๐ฟ(๐ฃ) by the points of ๐ โฉ ๐(๐ฃ). When ๐ฟ = ๐ฟ(๐ฃ), we
also write cost(๐ฟ) to denote cost(๐ฃ). If ๐ฃ is a leaf vertex, then its cost is set to 0.
Definition 2.6 (WB-1 bound). For any semi-permutation ๐, an ordering ๐ of the auxiliary
columns in โ, and the corresponding partitioning tree ๐ = ๐(๐), the (weak) WB-1 bound of
๐ with respect to ๐ is: WB๐ (๐) = WB๐ (๐) = ๐ฃโ๐(๐) cost(๐ฃ). The strong WB-1 bound of ๐ is
ร
WB(๐) = max๐ WB๐ (๐), where the maximum is taken over all permutations ๐ of the lines in โ.
It is well known that the WB-1 bound is a lower bound on the optimal solution cost:
Claim 2.7. For any semi-permutation ๐, WB(๐) โค 2 ยท OPT(๐).
The original proof of this fact is due to Wilber [29], which was later presented in the geometric
view by Demaine et al. [11], via the notion of independent rectangles. In Section 8, we include a
direct geometric proof of this fact.
We note a simple observation, that the cost can be bounded by the number of points on the
smaller side.
Observation 2.8. Let ๐ be a semi-permutation, ๐ an ordering of the auxiliary columns in โ, and
let ๐ = ๐(๐) be the corresponding partitioning tree. Let ๐ฃ โ ๐(๐) be any inner vertex of the tree,
whose two child vertices are denoted by ๐ฃ 1 and ๐ฃ2 . Then cost(๐ฃ) โค 2 min{|๐ โฉ ๐(๐ฃ 1 )|, |๐ โฉ ๐(๐ฃ 2 )|}.
Proof. For simplicity, we denote ๐ 0 = ๐ โฉ ๐(๐ฃ1 ) and ๐ 00 = ๐ โฉ ๐(๐ฃ 2 ). Assume w.l.o.g. that
|๐ 0 | โค |๐ 00 |. Notice that, if the pair (๐ ๐ , ๐ ๐+1 ) of points in ๐(๐ฃ) define a crossing of ๐ฟ(๐ฃ), then one
of ๐ ๐ , ๐ ๐+1 must lie in ๐ 0. Every point ๐ ๐ โ ๐ 0 may participate in at most two pairs of points that
define crossings: the pairs (๐ ๐โ1 , ๐ ๐ ) and (๐ ๐ , ๐ ๐+1 ). Therefore, the total number of crossings of
๐ฟ(๐ฃ) is at most 2|๐ 0 |.
3Also called Interleaving bound [12], the first Wilber bound, โinterleave lower boundโ [29], or alternation
bound [18]
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 12
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
Figure 2: An illustration of a split of ๐ by โ 0 = {๐ฟ1 , ๐ฟ2 , ๐ฟ3 }.
3 Geometric decomposition theorems
In this section, we develop several technical tools that will allow us to decompose a given
instance into a number of sub-instances. We then analyze the optimal solution costs and the
Wilber bound values for the resulting subinstances.
3.1 Split instances
Consider a semi-permutation ๐. We define the split instances with respect to any subset โ 0 โ โ
of the auxiliary columns for ๐: Notice that the lines in โ 0 partition the bounding box ๐ต into a
collection of internally disjoint strips, that we denote by {๐1 , . . . , ๐ ๐ } where ๐ = |โ 0 | + 1. We can
then define the strip instances ๐๐ โ ๐ as containing all vertices of ๐ โฉ ๐ ๐ for all 1 โค ๐ โค ๐, and
the compressed instance ๐, ห that is obtained by collapsing, for each 1 โค ๐ โค ๐, all active columns
๐
that lie in strip ๐ ๐ , into a single column. We call these resulting instances (๐ห , {๐๐ } ๐=1 ) a split of ๐
by โ 0. See Figure 2.
๐
Observation 3.1. Let โ 0 โ โ be a collection of lines and (๐ห , {๐๐ } ๐=1 ) be a split of ๐ by โ 0. Then
โข ๐ ๐(๐ ๐ ) = ๐(๐)
ร
โข ๐ ๐(๐๐ )) = ๐(๐)
ร
ห โค๐
โข ๐(๐)
The first property holds since ๐ is a semi-permutation.
Consider an arbitrary ordering ๐ of the lines in โ, such that the lines of โ 0 appear at the
beginning of ๐. The lines in โ 0 split ๐ naturally into ๐ + 1 orderings. Let ๐1 , . . . , ๐ ๐ be the strips
obtained from partitioning box ๐ต by โ 0, and for each ๐ โ [๐], โ ๐ is a collection of lines in strip ๐ ๐ .
Now, ๐๐ can be defined by naturally inducing ๐ to the lines in โ ๐ , and ๐ห is the ordering of lines
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 13
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
in โ 0 induced by ๐. We say that ๐, ห ๐1 , . . . , ๐ ๐ are the split orderings of ๐ by โ 0. Similarly, the
lines โ also split the partitioning tree ๐ = ๐(๐) into ๐
0 e = ๐(๐)ห and ๐1 , . . . , ๐๐ where ๐๐ = ๐(๐๐ )
for all ๐ โ [๐]. These partitioning trees are called the split partitioning trees of ๐ by โ 0.
๐
Observation 3.2. For โ 0 โ โ and ordering ๐, let (๐ห , {๐๐ } ๐=1 ) and ( ๐,
ห {๐๐ }) be the split instances
and split orderings respectively. Then,
๐
ร
ห = WB๐ (๐)
WB๐๐ (๐๐ ) + WB๐ห (๐)
๐=1
This property can be viewed as a โperfectโ decomposition property of the weak WB-1 bound
with respect to the split operation.
3.2 Decomposition theorem for the optimal solution
We prove the following recurrence about the โsubadditivityโ property of OPT under the
decomposition into split instances.
๐
Theorem 3.3. Let โ 0 โ โ be a collection of lines and (๐ห , {๐๐ } ๐=1 ) be a split instance of ๐ by โ 0. Then
๐
ร
ห โค OPT(๐).
OPT(๐๐ ) + OPT(๐)
๐=1
๐
Proof. Let {๐ ๐ } ๐=1 be the strips partitioned by โ 0. Let ๐ be an optimal canonical solution for
๐, so that every point of ๐ lies on an active row and an active column for ๐. For each ๐, let ๐๐
denote the set of points of ๐ that lie in the strip ๐ ๐ . Since these points lie in the interior of the
ร๐
strip, ๐ = ๐=1 ๐๐ .
For each ๐, let โ ๐ denote the set of all rows ๐
, such that: (i) ๐
contains a point of ๐; (ii) ๐
contains
no point of ๐๐ ; and (iii) at least one point of ๐๐ lies on ๐
. Let ๐ ๐ = |โ ๐ |. We need the following
claim.
Claim 3.4. There is a feasible solution ๐ห to instance ๐,
ห containing at most ๐ ๐ ๐ points.
ร
Proof. We construct the solution ๐ห for ๐ห as follows. Consider ๐ โ [๐]. Let ๐ถ ๐ be the unique
column into which the columns lying in the strip ๐ ๐ were collapsed. For every point ๐ โ ๐๐ that
lies on a row ๐
โ โ ๐ , we add a new point ๐(๐) on the intersection of row ๐
and column ๐ถ ๐ to
the solution ๐. ห Once we process all strips ๐ โ [๐], we obtain a final set of points ๐. ห It is easy to
verify that |๐|ห = ๐ ๐ ๐ . In order to see that ๐ห is a feasible solution to instance ๐,
ร ห it is enough to
show that the set ๐ห โช ๐ห of points is satisfied. Notice that set ๐ โช ๐ of points is satisfied, and
set ๐ห โช ๐ห is obtained from ๐ โช ๐ by collapsing sets of active columns lying in each strip ๐ ๐ for
๐ โ [๐]. From Observation 2.4, the point set ๐ห โช ๐ห is satisfied.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 14
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
We now consider the strip instances {๐๐ } ๐โ[๐] and prove the following claim, that will complete
the proof of the lemma.
Claim 3.5. For each ๐ โ [๐], OPT(๐๐ ) โค |๐๐ | โ ๐ ๐ .
Proof. Notice first that the point set ๐๐ โช ๐๐ must be satisfied. We will modify point set ๐๐ , to
obtain another set ๐๐0, so that ๐๐0 remains a feasible solution for ๐๐ , and |๐๐0 | โค |๐๐ | โ ๐ ๐ .
In order to do so, we perform ๐ ๐ iterations. In each iteration, we will decrease the size of ๐๐
by at least one, while also decreasing the cardinality of the set โ ๐ of rows by exactly 1, and
maintaining the feasibility of the solution ๐๐ for ๐๐ .
In every iteration, we select two arbitrary rows ๐
and ๐
0, such that: (i) ๐
โ โ ๐ ; (ii) ๐
0 is an active
row for instance ๐๐ , and (iii) no point of ๐๐ โช ๐๐ lies strictly between rows ๐
and ๐
0. We collapse
the rows ๐
and ๐
0 into the row ๐
0. From Observation 2.4, the resulting new set ๐๐ of points
remains a feasible solution for instance ๐๐ . We claim that |๐๐ | decreases by at least 1. In order
to show this, it is enough to show that there are two points ๐, ๐ 0 โ ๐๐ โช ๐๐ , with ๐ โ ๐
, ๐ 0 โ ๐
0,
such that the ๐ฅ-coordinates of ๐ and ๐ 0 are the same; in this case, after we collapse the rows, ๐ฅ
and ๐ฅ 0 are mapped to the same point. Assume for contradiction that no such two points exist.
Let ๐ โ ๐
โฉ (๐๐ โช ๐๐ ), ๐ 0 โ ๐
0 โฉ ๐๐ be a pair of points with smallest horizontal distance. Such
points must exist since ๐
contains a point of ๐๐ and ๐
0 contains a point of ๐๐ . But then no other
point of ๐๐ โช ๐๐ lies in ๐,๐0 , so the pair (๐, ๐ 0) is not satisfied in ๐๐ โช ๐๐ , a contradiction.
3.3 Decomposition theorem for the strong WB-1 bound.
We prove the following recurrence about the strong WB-1 bound bound.
๐
Theorem 3.6. Let โ 0 โ โ be a collection of lines and (๐ห , {๐๐ } ๐=1 ) be a split instance of ๐ by โ 0. Then
๐
ร
ห +8
WB(๐) โค 4WB(๐) WB(๐๐ ) + ๐(|๐ |).
๐=1
We find this result somewhat surprising. One can think of the expression WB(๐)
ร
e + ๐โ[๐] WB(๐๐ )
as a WB-1 bound obtained by first cutting along the lines that serve as boundaries of the strips
๐ ๐ for ๐ โ [๐], and then starting to cut inside the individual strips afterwards. However, WB(๐)
is the maximum of WB๐ (๐) obtained over all possible orderings ๐, including those that do not
obey this cutting order.
The remainder of this section is dedicated to the proof of Theorem 3.6. For each 1 โค ๐ โค ๐, we
denote by โฌ๐ be the set of consecutive active columns containing the points of ๐๐ , and we refer
to it as a block. For brevity, we also say โWilber boundโ to mean the strong WB-1 bound in this
section.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 15
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
3.3.1 Forbidden points
For the sake of the proof, we need the notion of forbidden points. Let ๐ห be some semi-
permutation and โฬ be the set of auxiliary columns for ๐.ห Let ๐น โ ๐ห be a set of points that we
refer to as forbidden points. We now define the strong WB-1 bound with respect to the forbidden
points, WB๐น (๐).ห
Consider any permutation ๐ห of the lines in โฬ. Intuitively, WB๐น๐ห (๐)
ห counts all the crossings
ห but excludes all crossing pairs (๐, ๐ 0) where at least one of ๐, ๐ 0 lie
contributed to WB๐ห (๐)
in ๐น. Similar to WB(๐), we define WB๐น (๐)ห = max๐ห WB๐น (๐),
๐ห
ห where the maximum is over all
permutations ๐ห of the lines in โฬ.
Next, we define WB๐น๐ห (๐) ห more formally. Let ๐ = ๐( ๐) ห be the partitioning tree associated with ๐. ห
For each vertex ๐ฃ โ ๐(๐), let ๐ฟ = ๐ฟ(๐ฃ) be the line that belongs to ๐ฃ, and let Cr๐ห (๐ฟ) be the set of
all crossings (๐, ๐ 0) that contribute to cost(๐ฟ); that is, ๐ and ๐ 0 are two points that lie in the strip
๐(๐ฃ) on two opposite sides of ๐ฟ, and no other point of ๐ห โฉ ๐(๐ฃ) lies between the row of ๐ and
the row of ๐ 0. Let Cr๐ห = ๐ฟโโฬ Cr๐ห (๐ฟ). Observe that WB๐ห (๐) = | Cr๐ห | by definition. We say that
ร
a crossing (๐, ๐ 0) โ Cr๐ห (๐ฟ) is forbidden iff at least one of ๐, ๐ 0 lie in ๐น; otherwise the crossing is
allowed. We let Cr๐น๐ห (๐ฟ) be the set of crossings obtained from Cr๐ห (๐ฟ) by discarding all forbidden
crossings. We then let Cr๐น๐ห = ๐ฟโโฬ Cr๐น๐ห (๐ฟ), and WB๐น๐ห (๐) ห = | Cr๐น |.
ร
๐ห
We emphasize that WB๐น (๐)ห is not necessarily the same as WB(๐ห \ ๐น), as some crossings of the
ห ห
instance ๐ \ ๐น may not correspond to allowed crossings of instance ๐.
3.3.2 Proof overview and notation
Consider first the compressed instance ๐, ห that is a semi-permutation. We denote its set of
active columns by ๐ห = {๐ถ1 , . . . , ๐ถ ๐ }, where the columns are indexed in their natural left-to-right
order. Therefore, ๐ถ ๐ is the column that was obtained by collapsing all active columns in strip
๐ ๐ . It would be convenient for us to slightly modify the instance ๐ห by simply multiplying
all ๐ฅ-coordinates of the points in ๐ห and of the columns in ๐ห by factor 2. Note that this does
not affect the value of the optimal solution or of the Wilber bound, but it ensures that every
consecutive pair of columns in ๐ห is separated by a column with an integral ๐ฅ-coordinate. We let
โฬ be the set of all vertical lines with half-integral coordinates in the resulting instance ๐. ห
Similarly, we modify the original instance ๐, by inserting, for every consecutive pair โฌ๐ , โฌ๐+1 of
blocks, a new column with an integral coordinate that lies between the columns of โฌ๐ and the
columns of โฌ๐+1 . This transformation does not affect the optimal solution cost or the value of
the Wilber bound. For all 1 โค ๐ โค ๐, we denote ๐ ๐ = |โฌ๐ |. We denote by โ the set of all vertical
lines with half-integral coordinates in the resulting instance ๐.
๐ +1
n o
Consider any block โฌ๐ . We denote by โ ๐ = ๐ฟ1๐ , . . . , ๐ฟ ๐ ๐ the set of ๐ ๐ + 1 consecutive vertical
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 16
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
๐ +1
lines in โ, where ๐ฟ1๐ appears immediately before the first column of โฌ๐ , and ๐ฟ ๐ ๐ appears
immediately after the last column of โฌ๐ . Notice that โ = ๐
ร
๐=1 โ ๐ .
Recall that our goal is to show that WB(๐) โค 4WB(๐) ห + 8 ร ๐ WB(๐๐ ) + ๐(|๐ |). In order to do so,
๐=1
we fix a permutation ๐ of โ that maximizes WB๐ (๐), so that WB(๐) = WB๐ (๐). We then gradually
ห โฅ WB๐ (๐)/4 โ 2 ร ๐ WB(๐๐ ) โ ๐(|๐ |).
transform it into a permutation ๐ห of โฬ, such that WB๐ห (๐) ๐=1
This will prove that WB(๐) โค 4WB(๐) ห + 8 ร ๐ WB(๐๐ ) + ๐(|๐ |).
๐=1
In order to perform this transformation, we will process every block โฌ๐ one-by-one. When
block โฌ๐ is processed, we will โconsolidateโ all lines of โ ๐ , so that they will appear almost
consecutively in the permutation ๐, and we will show that this process does not increase
the Wilber bound by too much. The final permutation that we obtain after processing every
block โฌ๐ can then be naturally transformed into a permutation ๐ห of โฬ, whose Wilber bound
cost is similar. The main challenge is to analyze the increase in the Wilber bound in every
iteration. In order to facilitate the analysis, we will work with the Wilber bound with respect
to forbidden points. Specifically, we will define a set ๐น โ ๐ of forbidden points, such that
ร๐
WB๐น๐ (๐) โฅ WB๐ (๐)/4 โ ๐=1 WB(๐๐ ). For every block โฌ๐ , we will also define a bit ๐ ๐ โ {0, 1},
that will eventually guide the way in which the lines of โ ๐ are consolidated. As the algorithm
progresses, we will modify the set ๐น of forbidden points by discarding some points from it,
and we will show that the increase in the Wilber bound with respect to the new set ๐น is small
relatively to the original Wilber bound with respect to the old set ๐น. We start by defining the set
๐น of forbidden points, and the bits ๐ ๐ for the blocks โฌ๐ . We then show how to use these bits in
order to transform permutation ๐ of โ into a new permutation ๐0 of โ, which will in turn be
transformed into a permutation ๐ห of โฬ.
From now on we assume that the permutation ๐ of the lines in โ is fixed.
3.3.3 Defining the set of forbidden points
Consider any block โฌ๐ , for 1 โค ๐ โค ๐. We denote by ๐ฟโ๐ โ โ ๐ the vertical line that appears first in
the permutation ๐ among all lines of โ ๐ , and we denote by ๐ฟโโ๐
โ โ ๐ the line that appears last in
๐ among all lines of โ ๐ .
We perform ๐ iteration. In iteration ๐, for 1 โค ๐ โค ๐, we consider the block โฌ๐ . We let ๐ ๐ โ {0, 1}
be a bit chosen uniformly at random, independently from all other random bits. If ๐ ๐ = 0, then
all points of ๐๐ that lie to the left of ๐ฟโ๐ are added to the set ๐น of forbidden points; otherwise, all
points of ๐๐ that lie to the right of ๐ฟโ๐ are added to the set ๐น of forbidden points. We show that
the expected number of the remaining crossings is large.
ร๐
Claim 3.7. The expectation, over the choice of the bits ๐ ๐ , of | Cr๐น๐ | is at least | WB(๐)|/4 โ ๐=1 WB(๐ ๐ ).
Proof. Consider any crossing (๐, ๐ 0) โ Cr๐ . We consider two cases. Assume first that there is
some index ๐, such that both ๐ and ๐ 0 belong to ๐๐ , and they lie on opposite sides of ๐ฟโ๐ . In
this case, (๐, ๐ 0) becomes a forbidden crossing with probability 1. However, the total number
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 17
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
of all such crossings is bounded by WB(๐๐ ). Indeed, if we denote by โฬ ๐ the set of all vertical
lines with half-integral coordinates for instance ๐๐ , then permutation ๐ of โ naturally induces
permutation ๐๐ of โฬ ๐ . Moreover, any crossing (๐, ๐ 0) โ Cr๐ with ๐, ๐ 0 โ ๐๐ must also contribute
to the cost of ๐๐ in instance ๐๐ . Since the cost of ๐๐ is bounded by ๐ ๐ต(๐๐ ), the number of
crossings (๐, ๐ 0) โ Cr๐ with ๐, ๐ 0 โ ๐๐ is bounded by ๐ ๐ต(๐๐ ).
Consider now any crossing (๐, ๐ 0) โ Cr๐ , and assume that there is no index ๐, such that
both ๐ and ๐ 0 belong to ๐๐ , and they lie on opposite sides of ๐ฟโ๐ . Then with probability
at least 1/4, this crossing remains allowed. Therefore, the expectation of | Cr๐น๐ | is at least
ร๐ ร๐ ร๐
| Cr๐ |/4 โ ๐=1 WB(๐๐ ) = | WB๐ (๐)|/4 โ ๐=1 WB(๐๐ ) = | WB(๐)|/4 โ ๐=1 WB(๐๐ ).
From the above claim, there is a choice of the bits ๐1 , . . . , ๐ ๐ , such that, if we define the set ๐น
ร๐
of forbidden points with respect to these bits as before, then | Cr๐น๐ | โฅ WB(๐)/4 โ ๐=1 WB(๐๐ ).
From now on we assume that the values of the bits ๐1 , . . . , ๐ ๐ are fixed, and that the resulting set
ร๐
๐น of forbidden points satisfies that | Cr๐น๐ | โฅ WB(๐)/4 โ ๐=1 WB(๐๐ ).
3.3.4 Transforming ๐ into ๐0
We now show how to transform the original permutation ๐ of โ into a new permutation ๐0 of
โ, which we will later transform into a permutation ๐ห of โฬ. We perform ๐ iterations. The input
to the ๐th iteration is a permutation ๐๐ of โ and a subset ๐น๐ โ ๐น of forbidden points. The output
of the iteration is a new permutation ๐๐+1 of โ, and a set ๐น๐+1 โ ๐น๐ of forbidden points. The final
permutation is ๐0 = ๐ ๐+1 , and the final set ๐น ๐+1 of forbidden points will be empty. The input to
the first iteration is ๐1 = ๐ and ๐น1 = ๐น. We now fix some 1 โค ๐ โค ๐, and show how to execute the
๐th iteration. Intuitively, in the ๐th iteration, we consolidate the lines of โ ๐ . Recall that we have
denoted by ๐ฟโ๐ , ๐ฟโโ
๐
โ โ ๐ the first and the last lines of โ ๐ , respectively, in the permutation ๐. We
only move the lines of โ ๐ in iteration ๐, so this ensures that, in permutation ๐๐ , the first line of
โ ๐ that appears in the permutation is ๐ฟโ๐ , and the last line is ๐ฟโโ ๐
.
We now describe the ๐th iteration. Recall that we are given as input a permutation ๐๐ of the lines
of โ, and a subset ๐น๐ โ ๐น of forbidden points. We consider the block โฌ๐ and the corresponding
bit ๐ ๐ .
Assume first that ๐ ๐ = 0; recall that in this case, all points of ๐ that lie on the columns of โฌ๐ to
the left of ๐ฟโ๐ are forbidden (see Figure 3). We start by switching the locations of ๐ฟโ๐ and ๐ฟ1๐ in the
permutation ๐๐ (recall that ๐ฟ1๐ is the leftmost line in โ ๐ ). Therefore, ๐ฟ1๐ becomes the first line of
โ ๐ in the resulting permutation. Next, we consider the location of line ๐ฟโโ ๐
in ๐๐ , and we place the
๐ +1 ๐
lines ๐ฟ ๐ ๐ , ๐ฟ2๐ , ๐ฟ3๐ , . . . , ๐ฟ ๐ ๐ in that location, in this order. This defines the new permutation ๐๐+1 .
Assume now that ๐ ๐ = 1; recall that in this case, all points of ๐ that lie on the columns of โฌ๐ to
๐ +1
the right of ๐ฟโ๐ are forbidden (see Figure 3). We start by switching the locations of ๐ฟโ๐ and ๐ฟ ๐ ๐
๐ +1 ๐ +1
in the permutation ๐๐ (recall that ๐ฟ ๐ ๐ is the rightmost line in โ ๐ ). Therefore, ๐ฟ ๐ ๐ becomes
the first line of โ ๐ in the resulting permutation. Next, we consider the location of line ๐ฟโโ๐
in
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 18
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
๐๐ = 0
โฌ๐ โฌ๐
๐ฟ4๐
๐ฟ3๐
๐ฟ2๐
๐ฟ4๐ ๐ฟ5๐
๐ฟ1๐
๐ฟ2๐
๐ฟ5๐ ๐ฟ1๐
๐ฟ3๐
๐๐ ๐๐+1
๐๐ = 1
โฌ๐ โฌ๐
๐ฟ4๐
๐ฟ3๐
๐ฟ2๐
๐ฟ4๐ ๐ฟ1๐
๐ฟ1๐
๐ฟ2๐
๐ฟ5๐
๐ฟ3๐ ๐ฟ5๐
๐๐ ๐๐+1
Figure 3: Modification from ๐๐ to ๐๐+1 . In the figure, โ ๐ = {๐ฟ1๐ , . . . , ๐ฟ5๐ }, ๐ฟโ๐ = ๐ฟ3๐ and ๐ฟโโ
๐
= ๐ฟ4๐ .
Points with horizontal strips are forbidden.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 19
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
๐
๐๐ , and we place the lines ๐ฟ1๐ , ๐ฟ2๐ , ๐ฟ3๐ , . . . , ๐ฟ ๐ ๐ in that location, in this order. This defines the new
permutation ๐๐+1 .
Lastly, we discard from ๐น๐ all points that lie on the columns of โฌ๐ , obtaining the new set ๐น๐+1 of
forbidden points.
Once every block โฌ๐ is processed, we obtain a final permutation ๐ ๐+1 that we denote by ๐0, and
the final set ๐น ๐+1 = โ
of forbidden lines. The following lemma is central to our analysis. It shows
that the Wilber bound does not decrease by much after every iteration. The Wilber bound is
defined with respect to the appropriate sets of forbidden points.
Lemma 3.8. For all 1 โค ๐ โค ๐, WB๐น๐๐+1
๐+1
(๐) โฅ WB๐น๐๐๐ (๐) โ WB(๐๐ ) โ ๐(|๐๐ |).
Assume first that the lemma is correct. Recall that we have ensured that WB๐น๐11 (๐) = WB๐น๐ (๐) โฅ
ร๐
WB(๐)/4 โ ๐=1 WB(๐๐ ). Since ๐น ๐+1 = โ
, this will ensure that:
ร ร
WB๐0 (๐) โฅ WB๐น๐ (๐) โ WB(๐๐ ) โ ๐(|๐ |) โฅ WB(๐)/4 โ 2 WB(๐๐ ) โ ๐(|๐ |).
๐ ๐
We now focus on the proof of the lemma.
Proof. In order to simplify the notation, we denote ๐๐ by ๐, ห
ห ๐๐+1 by ๐ห 0. We also denote ๐น๐ by ๐น,
and ๐น๐+1 by ๐นห 0.
Consider a line ๐ฟ โ โ. Recall that Cr๐ห (๐ฟ) is the set of all crossings that are charged to the line
ห
๐ฟ in permutation ๐.ห Recall that Cr๐น๐ห (๐ฟ) โ Cr๐ห (๐ฟ) is obtained from the set Cr๐ห (๐ฟ) of crossings,
ห0
by discarding all crossings (๐, ๐ 0) where ๐ โ ๐นห or ๐ 0 โ ๐นห holds. The set Cr๐น๐ห 0 (๐ฟ) of crossings is
defined similarly.
We start by showing that for every line ๐ฟ โ โ that does not lie in โ ๐ , the number of crossings
ห0 ห
charged to it does not decrease, that is, Cr๐น๐ห 0 (๐ฟ) โฅ Cr๐น๐ห (๐ฟ).
ห0 ห
Claim 3.9. For every line ๐ฟ โ โ \ โ ๐ , Cr๐น๐ห 0 (๐ฟ) โฅ Cr๐น๐ห (๐ฟ).
Proof. Consider any line ๐ฟ โ โ \ โ ๐ . Let ๐ฃ โ ๐(๐( ๐))ห be the vertex of the partitioning tree ๐( ๐) ห
corresponding to ๐ to which ๐ฟ belongs, and let ๐ = ๐(๐ฃ) be the corresponding strip. Similarly,
ห
we define ๐ฃ 0 โ ๐(๐(๐ห 0)) and ๐0 = ๐(๐ฃ 0) with respect to ๐ห 0. Recall that ๐ฟโ๐ is the first line of โ ๐ to
appear in the permutation ๐, and ๐ฟโโ ๐
is the last such line. We now consider five cases.
โข Case 1. The first case happens if ๐ฟ appears before line ๐ฟโ๐ in the permutation ๐. ห Notice
that the prefixes of the permutations ๐ห and ๐ห are identical up to the location in which ๐ฟโ๐
0
ห Therefore, ๐ = ๐0, and Cr๐ห (๐ฟ) = Cr๐ห 0 (๐ฟ). Since ๐นห 0 โ ๐น,
appears in ๐. ห every crossing that is
ห ห0 ห0 ห
ห So Cr๐น๐ห (๐ฟ) โ Cr๐น๐ห 0 (๐ฟ), and Cr๐น๐ห 0 (๐ฟ) โฅ Cr๐น๐ห (๐ฟ).
forbidden in ๐ห 0 was also forbidden in ๐.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 20
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
๐๐ = 0
โฌ๐ โฌ๐
๐1 ๐1
๐ ๐
๐2 ๐2
๐ฟ4๐
๐ฟ3๐
๐ฟ4๐
๐ฟ2๐
๐ฟ1๐ ๐ฟ5๐
๐ฟ2๐
๐ฟ5๐
โฒ
๐ฟ ๐ฟ1๐ ๐ฟ
๐ฟโ๐
๐๐ ๐๐+1
ห ห0
Figure 4: Illustration of the injective mapping of each crossing in Cr๐น๐ห (๐ฟ) to a crossing in Cr๐น๐ห 0 (๐ฟ).
Points with horizontal strips are forbidden points from ๐น. ห
โข Case 2. The second case happens if ๐ฟ appears after ๐ฟโโ ๐
in ๐.
ห Notice that, if we denote by
โ โ โ the set of all lines of โ that lie before ๐ฟ in ๐, and define โ 00 similarly for ๐ห 0, then
0 ห
ห0 ห
โ 0 = โ 00. Therefore, ๐ = ๐0 holds. Using the same reasoning as in Case 1, Cr๐น๐ห 0 (๐ฟ) โฅ Cr๐น๐ห (๐ฟ).
โข Case 3. The third case is when ๐ฟ appears between ๐ฟโ๐ and ๐ฟโโ ๐
in ๐,
ห but neither boundary of
the strip ๐ belongs to โ ๐ . If we denote by โ 0 โ โ \ โ ๐ the set of all lines of โ \ โ ๐ that lie
before ๐ฟ in ๐,
ห and define โ 00 โ โ \ โ ๐ similarly for ๐ห 0, then โ 0 = โ 00. Therefore, ๐ = ๐0
ห0 ห
holds. Using the same reasoning as in Cases 1 and 2, Cr๐น๐ห 0 (๐ฟ) โฅ Cr๐น๐ห (๐ฟ).
Case 4. The fourth case is when ๐ฟ appears between ๐ฟโ๐ and ๐ฟโโ ๐
in the permutation ๐,
ห
and the left boundary of ๐ belongs to โ ๐ . Notice that the left boundary of ๐ must either
coincide with ๐ฟโ๐ , or appear to the right of it.
Assume first that ๐ ๐ = 0, so we have replaced ๐ฟโ๐ with the line ๐ฟ1๐ , that lies to the left of ๐ฟโ๐ .
Since no other lines of โ ๐ appear in ๐ห 0 until the original location of line ๐ฟโโ๐
, it is easy to
verify that the right boundary of ๐0 is the same as the right boundary of ๐, and its left
boundary is the line ๐ฟ1๐ , that is, we have pushed the left boundary to the left. In order to
ห0 ห ห
prove that | Cr๐น๐ห 0 (๐ฟ)| โฅ | Cr๐น๐ห (๐ฟ)|, we map every crossing (๐ 1 , ๐2 ) โ Cr๐น๐ห (๐ฟ) to some crossing
ห0 ห
(๐ 10 , ๐20 ) โ Cr๐น๐ห 0 (๐ฟ), so that no two crossings of Cr๐น๐ห (๐ฟ) are mapped to the same crossing of
ห0
Cr๐น๐ห 0 (๐ฟ).
ห
Consider any crossing (๐ 1 , ๐2 ) โ Cr๐น๐ห (๐ฟ) (see Figure 4). We know that ๐ 1 , ๐2 โ ๐, and they
lie on opposite sides of ๐ฟ. We assume w.l.o.g. that ๐ 1 lies to the left of ๐ฟ. Moreover, no
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 21
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
point of ๐ โฉ ๐ lies between the row of ๐ 1 and the row of ๐ 2 . It is however possible that
(๐ 1 , ๐2 ) is not a crossing of Cr๐ห 0 (๐ฟ), since by moving the left boundary of ๐ to the left, we
add more points to the strip, some of which may lie between the row of ๐ 1 and the row
of ๐ 2 . Let ๐ด be the set of all points that lie between the row of ๐ 1 and the row of ๐2 in ๐0.
Notice that the points of ๐ด are not forbidden in ๐นห 0. Let ๐ โ ๐ด be the point of ๐ whose row
is closest to the row of ๐ 2 ; if ๐ด = โ
, then we set ๐ = ๐1 . Then (๐, ๐2 ) defines a crossing in
ห0
Cr๐ห 0 (๐ฟ), and, since neither point lies in ๐นห 0, (๐, ๐2 ) โ Cr๐น0 (๐ฟ). In this way, we map every
๐ห
๐นห ห0
crossing (๐ 1 , ๐2 ) โ Cr๐ห (๐ฟ) to some crossing (๐1 , ๐2 ) โ Cr๐น๐ห 0 (๐ฟ). It is easy to verify that no
0 0
ห ห0
two crossings of Cr๐น๐ห (๐ฟ) are mapped to the same crossing of Cr๐น๐ห 0 (๐ฟ). We conclude that
ห0 ห
| Cr๐น๐ห 0 (๐ฟ)| โฅ | Cr๐น๐ห (๐ฟ)|.
Lastly, assume that ๐ ๐ = 1. Recall that the set of all points of ๐ lying between ๐ฟโ๐ and
๐ +1 ๐ +1
๐ฟ ๐ ๐ is forbidden in ๐นห but not in ๐นห 0, and that we have replaced ๐ฟโ๐ with the line ๐ฟ ๐ ๐ , that
lies to the right of ๐ฟโ๐ . Therefore, the right boundary of ๐ remains the same, and the left
ห0 ห
boundary is pushed to the right. In order to prove that | Cr๐น๐ห 0 (๐ฟ)| โฅ | Cr๐น๐ห (๐ฟ)|, we show
ห ห0
that every crossing (๐ 1 , ๐2 ) โ Cr๐น๐ห (๐ฟ) belongs to Cr๐น๐ห 0 (๐ฟ). Indeed, consider any crossing
ห
(๐ 1 , ๐2 ) โ Cr๐น๐ห (๐ฟ). We know that ๐ 1 , ๐2 โ ๐, and they lie on opposite sides of ๐ฟ. We assume
w.l.o.g. that ๐ 1 lies to the left of ๐ฟ. Since ๐ 1 cannot be a forbidden point, it must lie to the
๐ +1
right of ๐ฟ ๐ ๐ . Moreover, no point of ๐ โฉ ๐ lies between the row of ๐1 and the row of ๐ 2 . It
ห0
is now easy to verify that (๐ 1 , ๐2 ) is also a crossing in Cr๐น๐ห 0 (๐ฟ).
โข Case 5. The fifth case happens when ๐ฟ appears between ๐ฟโ๐ and ๐ฟโโ ๐
in the permutation ๐,
ห
and the right boundary of ๐ belongs to โ ๐ . This case is symmetric to the fourth case and is
analyzed similarly.
It now remains to analyze the crossings of the lines in โ ๐ . We do so in the following two
๐ +1
claims. The first claim shows that switching ๐ฟโ๐ with ๐ฟ1๐ or ๐ฟ ๐ ๐ does not decrease the number of
crossings.
ห0 ห ห0 ๐ +1 ห
Claim 3.10. If ๐ = 0, then | Cr๐น๐ห 0 (๐ฟ1๐ )| โฅ | Cr๐น๐ห (๐ฟโ๐ )|; if ๐ = 1, then | Cr๐น๐ห 0 (๐ฟ ๐ ๐ )| โฅ | Cr๐น๐ห (๐ฟโ๐ )|.
Proof. Assume first that ๐ = 0, so we have replaced ๐ฟโ๐ with ๐ฟ1๐ in the permutation. As before,
we let ๐ฃ โ ๐(๐( ๐))ห be the vertex to which ๐ฟโ๐ belongs, and we let ๐ = ๐(๐ฃ) be the corresponding
strip. Similarly, we define ๐ฃ 0 โ ๐(๐( ๐ห 0)) and ๐0 = ๐(๐ฃ 0) with respect to line ๐ฟ1๐ and permutation
๐ห 0. Notice that, until the appearance of ๐ฟโ๐ in ๐,
ห the two permutations are identical. Therefore,
๐ = ๐ must hold. Recall also that all points of ๐ that lie between ๐ฟโ๐ and ๐ฟ1๐ are forbidden in
0
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 22
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
ห but not in ๐นห 0. In order to show that | Cr๐นห 00 (๐ฟ1 )| โฅ | Cr๐นห (๐ฟโ )|, it is enough to show that every
๐น, ๐ห ๐ ๐ห ๐
ห ห0
crossing (๐ 1 , ๐2 ) โ Cr๐น๐ห (๐ฟโ๐ ) also lies in Cr๐น๐ห 0 (๐ฟ1๐ ).
ห
Consider now some crossing (๐1 , ๐2 ) โ Cr๐น๐ห (๐ฟโ๐ ). Recall that one of ๐1 , ๐2 must lie to the left of ๐ฟโ๐
and the other to the right of it, with both points lying in ๐. Assume w.l.o.g. that ๐ 1 lies to the left
ห it must lie to the left of ๐ฟ1 . Moreover, no point of ๐ โฉ ๐ may lie between the
of ๐ฟโ๐ . Since ๐1 โ ๐น, ๐
ห0
row of ๐ 1 and the row of ๐ 2 . It is then easy to verify that (๐1 , ๐2 ) is also a crossing in Cr๐น๐ห 0 (๐ฟ1๐ ),
ห0 ห
and so | Cr๐น๐ห 0 (๐ฟ1๐ )| โฅ | Cr๐น๐ห (๐ฟโ๐ )|.
The second case, when ๐ = 1, is symmetric.
ห
Lastly, we show that for all lines ๐ฟ โ โ ๐ \ ๐ฟโ๐ , their total contribution to Cr๐น๐ห is small.
๐นห
๐ฟโโ ๐ \ { ๐ฟโ๐ } | Cr ๐ห (๐ฟ)| โค WB(๐๐ ) + ๐(|๐๐ |).
ร
Claim 3.11.
Assume first that the claimห is correct. We have shown so far that the total contribution of
all lines in โ ๐ \ ๐ฟโ๐ to Cr๐น๐ห is at most WB(๐๐ ) + ๐(|๐๐ |); that the contribution of one of the
๐ +1 ห0 ห
lines ๐ฟ1๐ , ๐ฟ ๐ ๐ to Cr๐น๐ห 0 is at least as large as the contribution of ๐ฟโ๐ to Cr๐น๐ห ; and that for every line
ห0 ห
๐ฟ โ โ ๐ , its contribution to Cr๐น๐ห 0 is at least as large as its contribution to Cr๐น๐ห . It then follows that
| Cr๐น๐ห 0 | โฅ | Cr๐น๐ห | โ WB(๐๐ ) + ๐(|๐๐ |), and so WB๐น๐๐+1 (๐) โฅ WB๐น๐๐๐ (๐) โ WB(๐๐ ) + ๐(|๐๐ |). Therefore,
ห0 ห
๐+1
in order to prove Lemma 3.8, it is now enough to prove Claim 3.11.
Proof. (Of Claim 3.11) Consider some line ๐ฟ โ โ ๐ \ ๐ฟโ๐ , and let ๐ฃ โ ๐(๐( ๐))
ห be the vertex to
which ๐ฟ belongs. Notice that ๐ฟ appears in ๐ห after ๐ฟโ๐ . Therefore, if ๐ = ๐(๐ฃ) is the strip that ๐ฟ
partitioned, then at least one of the boundaries of ๐ lies in โ ๐ . If exactly one boundary of ๐
lies in โ ๐ , then we say that ๐ is an external strip; otherwise, we say that ๐ is an internal strip.
Consider now some crossing (๐, ๐ 0) โ Cr๐ห (๐). Since ๐ฟ โ โ ๐ , and at least one boundary of ๐ lies
in โ ๐ , at least one of the points ๐, ๐ 0 must belong to ๐๐ . If exactly one of ๐, ๐ 0 lies in ๐๐ , then
we say that (๐, ๐ 0) is a type-1 crossing; otherwise it is a type-2 crossing. Notice that, if ๐ is an
internal strip, then only type-2 crossings of ๐ฟ are possible. We now bound the total number of
type-1 and type-2 crossings separately, in the following two observations.
ร
Observation 3.12. The total number of type-2 crossings in ๐ฟโโ ๐ \ { ๐ฟโ๐ } Cr ๐ห (๐ฟ) is at most WB(๐๐ ).
Proof. Permutation ๐ห of the lines in โ naturally induces a permutation ๐ห ๐ of the lines in โ ๐ . The
number of type-2 crossings charged to all lines in โ ๐ is then at most WB๐ห ๐ (๐๐ ) โค WB(๐๐ ).
๐ฟโโ ๐ \ { ๐ฟโ๐ } Cr ๐ห (๐ฟ) โค ๐(|๐๐ |).
ร
Observation 3.13. The total number of type-1 crossings in
Proof. Consider a line ๐ฟ โ โ ๐ \ ๐ฟโ๐ , and let ๐ be the strip that it splits. Recall that, if there are
any type-1 crossings in Cr๐ห (๐ฟ), then ๐ must be an external strip. Line ๐ฟ partitions ๐ into two new
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 23
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
strips, that we denote by ๐0 and ๐00. Notice that exactly one of these strips (say ๐0) is an internal
strip, and the other strip is external. Therefore, the points of ๐๐ โฉ ๐0 will never participate in
type-1 crossings again. Recall that, from Observation 2.8, the total number of crossings in Cr๐ห (๐ฟ)
is bounded by 2|๐0 โฉ ๐๐ |. We say that the points of ๐0 โฉ ๐๐ pay for these crossings. Since every
point of ๐๐ will pay for a type-1 crossing at most once, we conclude that the total number of
ร
type-1 crossings in ๐ฟโโ ๐ \{ ๐ฟโ } Cr๐ห (๐ฟ) is bounded by 2|๐๐ |.
๐
ร
We conclude that the total number of all crossings in ๐ฟโโ ๐ \ { ๐ฟโ๐ } Cr๐ห (๐ฟ) is at most WB(๐๐ )+๐(|๐ ๐ |).
ห ๐นห
Since, for every line ๐ฟ, Cr๐น๐ห (๐ฟ) โ Cr๐ห (๐ฟ), we get that ๐ฟโโ ๐ \ { ๐ฟโ } | Cr ๐ห (๐ฟ)| โค WB(๐๐ ) + ๐(|๐๐ |).
ร
๐
To summarize, we have transformed a permutation ๐ of โ into a permutation ๐0 of โ, and we
ร๐
have shown that WB๐0 (๐) โฅ WB(๐)/4 โ 2 ๐=1 WB(๐๐ ) โ ๐(|๐ |).
3.3.5 Transforming ๐0 into ๐ห
In this final step, we transform the permutation ๐0 of โ into a permutation ๐ห of โฬ, and we will
show that WB๐ห (๐) ห โฅ WB๐0 (๐) โ |๐ |.
The transformation is straightforward. Consider some block โฌ๐ , and the corresponding set
๐ +1
โ ๐ โ โ of lines. Recall that the lines in โ ๐ are indexed ๐ฟ1๐ , . . . , ๐ฟ ๐ ๐ in this left-to-right order,
๐ +1
where ๐ฟ1๐ appears to the left of the first column of โฌ๐ , and ๐ฟ ๐ ๐ appears to the right of the last
column of โฌ๐ . Recall also that, in the current permutation ๐0, one of the following happens:
๐ +1 ๐
either (i) line ๐ฟ1๐ appears in the permutation first, and lines ๐ฟ ๐ ๐ , ๐ฟ2๐ , . . . , ๐ฟ ๐ appear at some later
๐ +1
point consecutively in this order; or (ii) line ๐ฟ ๐ ๐ appears in the permutation first, and lines
๐
๐ฟ1๐ , ๐ฟ2๐ , . . . , ๐ฟ ๐ appear somewhere later in the permutation consecutively in this order. Therefore,
๐ ๐โ1 ๐ +1
for all 2 โค ๐ โค ๐, line ๐ฟ ๐ separates a strip whose left boundary is ๐ฟ ๐ and right boundary is ๐ฟ ๐ ๐ .
๐
It is easy to see that the cost of each such line ๐ฟ ๐ in permutation ๐0 is bounded by the number of
๐โ1 ๐
points of ๐ that lie on the unique active column that appears between ๐ฟ ๐ and ๐ฟ ๐ . The total
cost of all such lines is then bounded by |๐๐ |.
๐
Let ๐ห โ be a sequence of lines obtained from ๐0 by deleting, for all 1 โค ๐ โค ๐, all lines ๐ฟ2๐ , . . . , ๐ฟ ๐
from it. Then ๐ห โ naturally defines a permutation ๐ห of the set โฬ of vertical lines. Moreover,
from the above discussion, the total contribution of all deleted lines to WB๐0 (๐) is at most |๐ |,
so WB๐ห (๐)ห โฅ WB๐0 (๐) โ |๐ | โฅ WB(๐)/4 โ 2 ร๐ WB(๐๐ ) โ ๐(|๐ |). We conclude that WB(๐) ห โฅ
ห ห
WB๐ห (๐) โฅ WB(๐)/4 โ 2 ๐ WB(๐๐ ) โ ๐(|๐ |), and WB(๐) โค 4WB(๐) + 8 ๐ WB(๐๐ ) + ๐(|๐ |).
ร ร
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 24
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
4 Separation results for the strong Wilber bound
In this section we present our negative results, proving Theorem 1.1, and extend it to obtain a
separation result between the first and second Wilber bounds.
4.1 Basic tools
Our construction combines known input sequences and their properties, some of which have
been proved in the standard tree view of binary search trees. We discuss these facts in the
geometric context.
4.1.1 Monotonically increasing sequence
We say that an input set ๐ of points is monotonically increasing iff ๐ is a permutation, and
moreover for every pair ๐, ๐ 0 โ ๐ of points, if ๐.๐ฅ < ๐ 0 .๐ฅ, then ๐.๐ฆ < ๐ 0 .๐ฆ must hold. It is well
known that the value of the optimal solution of monotonically increasing sequences is low, and
we exploit this fact in our negative results.
Observation 4.1. If ๐ is a monotonically increasing set of points, then OPT(๐) โค |๐ | โ 1.
Proof. We order points in ๐ based on their ๐ฅ-coordinates as ๐ = {๐ 1 , . . . , ๐ ๐ } such that
๐ 1 .๐ฅ < ๐ 2 .๐ฅ < . . . < ๐ ๐ .๐ฅ. For each ๐ = 1, . . . , ๐ โ 1 we define ๐ ๐ = ((๐ ๐ ).๐ฅ, (๐ ๐+1 ).๐ฆ) and the set
๐ = {๐1 , . . . , ๐ ๐โ1 }. It is easy to verify that ๐ is a feasible solution for ๐.
4.1.2 Bit reversal sequence (BRS)
The bit-reversal sequence, first described by Wilber [29], is a family of explicit input sequences
whose optimal value is asymptotically largest possible, that is, OPT(๐) = ฮฉ(|๐ | log |๐ |). The
original sequence was described in the language of binary representation of strings. Here we
use the geometric variant of BRS, which is more convenient for our analysis.
Let ๐ โฅ 0 be an integer and โ โ โ and ๐ โ โ be subsets of active rows and columns such that
|โ| = |๐| = 2๐ . The level-๐ bit-reversal instance BRS(๐, โ, ๐) contains 2๐ points whose sets of
active rows and columns are exactly โ and ๐ respectively. The instances are defined inductively.
The level-0 instance BRS(0, {๐ถ}, {๐
}), containing a single point at the intersection of row ๐
and column ๐ถ. Assume now that we have defined, for all 1 โค ๐ 0 โค ๐, and any sets โ 0 , ๐ 0 of 2๐
0
integers, the corresponding instance BRS(๐ 0 , โ 0 , ๐ 0). We define instance BRS(๐ + 1, โ, ๐), where
|โ| = |๐| = 2๐+1 , as follows.
Consider the columns in ๐ in their natural left-to-right order, and define ๐๐๐ ๐ ๐ก to be the
first 2๐ columns and ๐๐๐๐ โ๐ก = ๐ \ ๐๐๐ ๐ ๐ก . Denote โ = {๐
1 , . . . , ๐
2๐+1 }, where the rows are
indexed in their natural bottom to top order, and let โ ๐๐ฃ๐๐ = {๐
2 , ๐
4 , . . . , ๐
2๐+1 } and โ ๐๐๐ =
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 25
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
{๐
1 , ๐
3 , . . . , ๐
2๐+1 โ1 } be the sets of all even-indexed and all odd-indexed rows, respectively.
Notice that |๐๐๐ ๐ ๐ก | = |๐๐๐๐ โ๐ก | = |โ ๐๐ฃ๐๐ | = |โ ๐๐๐ | = 2๐ . The instance BRS(๐ + 1, โ, ๐) is defined to
be BRS(๐, โ ๐๐๐ , ๐๐๐ ๐ ๐ก ) โช BRS(๐, โ ๐๐ฃ๐๐ , ๐๐๐๐ โ๐ก ). See Figure 5 for an illustration.
It is well-known [29] that, if ๐ is a bit-reversal sequence on ๐ points, then OPT(๐) โฅ ฮฉ(๐ log ๐).
Claim 4.2. Let ๐ = BRS(๐, ๐, โ), for any ๐ โฅ 0 and any sets ๐ and โ of columns and rows, respectively,
with |โ| = |๐| = 2๐ . Then |๐ | = 2๐ , and OPT(๐) โฅ WB2(๐) โฅ ฮฉ(|๐ | log |๐ |).
Next, we present two additional technical tools that we use in our construction.
4.1.3 Exponentially spaced columns
Recall that we defined the bit reversal instance BRS(โ , โ, ๐), where โ and ๐ are sets of 2โ
rows and columns, respectively, that serve in the resulting instance as the sets of active rows
and columns; the instance contains ๐ = 2โ points. In the Exponentially-Spaced BRS instance
ES-BRS(โ , โ), we are still given a set โ of 2โ rows that will serve as active rows in the resulting
instance, but we define the set ๐ of columns in a specific way. For an integer ๐, let ๐ถ ๐ be the
column whose ๐ฅ-coordinate is ๐ and ๐ contain, for each 0 โค ๐ < 2โ , the column ๐ถ2๐ . Denoting
โ
๐ = 2๐ = 22 , the ๐ฅ-coordinates of the columns in ๐ are {1, 2, 4, 8, . . . , ๐/2}. The instance is
then defined to be BRS(โ , โ, ๐) for this specific set ๐ of columns. Notice that the instance
contains ๐ = log ๐ = 2โ input points.
It is easy to see that any point set ๐ = ES-BRS(โ , โ) satisfies OPT(๐) = ฮฉ(๐ log ๐). We remark
that this idea of exponentially spaced columns is inspired by the instance used by Iacono [18]
to prove a gap between the weak WB-1 bound and OPT(๐). However, Iaconoโs instance is
tailored to specific partitioning tree ๐, and it is clear that there is another partitioning tree ๐ 0
with OPT(๐) = ฮ(๐ ๐ต๐ 0 (๐)). Therefore, this instance does not give a separation result for the
strong WB-1 bound, and in fact it does not provide negative results for the weak WB-1 bound
when the input point set is a permutation.
4.1.4 Cyclic shift of columns
Suppose we are given a point set ๐, and let ๐ = {๐ถ0 , . . . , ๐ถ ๐โ1 } be any set of columns indexed in
their natural left-to-right order, such that all points of ๐ lie on columns of ๐ (but some columns
may contain no points of ๐). Let 0 โค ๐ < ๐ be any integer. We denote by ๐ ๐ a cyclic shift of ๐
by ๐ units with respect to ๐, obtained as follows. For every point ๐ โ ๐ on column ๐ถ ๐ , we add a
new point ๐ ๐ to ๐ ๐ , that lies on the same row as ๐ and on column ๐ถ(๐+๐ ) mod ๐ . In other words,
we shift the point ๐ by ๐ steps to the right (with respect to ๐) in a circular manner. Equivalently,
we move the last ๐ columns of ๐ to the beginning of the instance. The following claim shows
that the value of the optimal solution does not decrease significantly in the shifted instance.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 26
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
Claim 4.3. Let ๐ be any point set that is a semi-permutation. Let 0 โค ๐ < ๐ be a shift value, and let
๐ 0 = ๐ ๐ be the instance obtained from ๐ by a cyclic shift of its points by ๐ units to the right. Then
OPT(๐ 0) โฅ OPT(๐) โ |๐ |.
Proof. Let ๐ 0 be an optimal canonical solution to instance ๐ 0. We partition ๐ 0 into two subsets:
set ๐10 consists of all points lying on the first ๐ columns with integral coordinates, and set ๐20
consists of all points lying on the remaining columns. We also partition the points of ๐ 0 into two
subsets ๐10 and ๐20 similarly. Notice that ๐10 โช ๐10 must be a satisfied set of points, and similarly,
๐20 โช ๐20 is a satisfied set of points. Our goal is to use these sets to construct a feasible solution
for ๐ of size |๐ | + |๐10 | + |๐20 | = |๐ | + OPT(๐ 0).
Next, we partition the set ๐ of points into two subsets: set ๐1 contains all points lying on the
last ๐ columns with integral coordinates, and set ๐2 contains all points lying on the remaining
columns. Since ๐1 and ๐2 are simply horizontal shifts of the sets ๐10 and ๐20 of points, we can
define a set ๐1 of |๐10 | points such that ๐1 is a canonical feasible solution for ๐1 , and we can define
a set ๐2 for ๐2 similarly. Let ๐ถ be a column with a half-integral ๐ฅ-coordinate that separates ๐1
from ๐2 (that is, all points of ๐1 lie to the right of ๐ถ while all points of ๐2 lie to its left.) We
construct a new set ๐ of points, of cardinality |๐ |, such that ๐1 โช ๐2 โช ๐ is a feasible solution to
instance ๐. In order to construct the point set ๐, for each point ๐ โ ๐, we add a point ๐ 0 with
the same ๐ฆ-coordinate, that lies on column ๐ถ, to ๐. Notice that |๐| = |๐ |.
We claim that ๐ โช (๐1 โช ๐2 ) is a feasible solution for ๐, and this will complete the proof. Consider
any two points ๐, ๐ โ ๐ โช (๐1 โช ๐2 ) โช ๐ that are not aligned. Let ๐ต1 and ๐ต2 be the strips obtained
from the bounding box ๐ต by partitioning it with column ๐ถ, so that ๐1 โ ๐ต1 and ๐2 โ ๐ต2 . If
both ๐ and ๐ lie in the interior of the same strip, say ๐ต1 , we are done since set ๐1 โช ๐1 of points
is satisfied. So, assume that one of the points (say ๐) lies in the interior of one of the strips
(say ๐ต1 ), while the other point either lies on ๐ถ, or in the interior of ๐ต2 . Then ๐ โ ๐1 โช ๐1 must
hold. Moreover, since ๐1 is a canonical solution for ๐1 , point ๐ lies on a row that is active for ๐1 .
Therefore, some point ๐ 0 โ ๐1 lies on the same row (where possibly ๐ 0 = ๐). But then a copy of
๐ 0 that was added to the set ๐ and lies on the column ๐ถ satisfies the pair (๐, ๐).
4.1.5 Partial costs of WB-1 bound
We use simple facts about the Wilber bound. The following is a property of any balanced binary
search trees.
Lemma 4.4. For any semi-permutation ๐, WB(๐) โค 2OPT(๐) โค ๐(๐(๐) log ๐(๐)).
Our analysis also uses partial costs of the WB-1 bound restricted to a subtree and a path.
Claim 4.5. Consider a set ๐ of points that is a semi-permutation, an ordering ๐ of the auxiliary columns
in โ and the corresponding partitioning tree ๐ = ๐(๐). Let ๐ฃ โ ๐(๐) be any vertex of the tree. Then the
following hold:
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 27
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
โข Let ๐๐ฃ be the subtree of ๐ rooted at ๐ฃ. Then
ร
cost(๐ข) = WB๐๐ฃ (๐ โฉ ๐(๐ฃ)) โค ๐(๐(๐ฃ) log(๐(๐ฃ)))
๐ขโ๐(๐๐ฃ )
โข Let ๐ข be any descendant vertex of ๐ฃ, and let ๐ be the unique path in ๐ connecting ๐ข to ๐ฃ. Then
ร
๐งโ๐(๐) cost(๐ง) โค 2๐(๐ฃ).
Proof. The first assertion follows from the definition of the weak WB-1 bound and Lemma 4.4.
We now prove the second assertion. Denote ๐ = (๐ฃ = ๐ฃ 1 , ๐ฃ2 , . . . , ๐ฃ ๐ = ๐ข). For all 1 < ๐ โค ๐, we
let ๐ฃ 0๐ be the unique sibling of the vertex ๐ฃ ๐ in the tree ๐. We also let ๐๐ be the set of points of ๐
that lie in the strip ๐(๐ฃ 0๐ ), and we let ๐ 0 be the set of all points of ๐ that lie in the strip ๐(๐ฃ ๐ ). It is
๐
easy to verify that ๐2 , . . . , ๐ ๐ , ๐ 0 are all mutually disjoint (since the strips {๐(๐ฃ 0๐ )} ๐=2 and ๐(๐ฃ ๐ )
ร๐
are disjoint), and that they are contained in ๐ โฉ ๐(๐ฃ). Therefore, ๐=2 |๐๐ | + |๐ 0 | โค ๐(๐ฃ).
From Observation 2.8, for all 1 โค ๐ < ๐, cost(๐ฃ ๐ ) โค 2๐(๐ฃ 0๐ ) = 2|๐๐ |, and cost(๐ฃ ๐ ) โค 2๐(๐ฃ ๐ ) = 2|๐ 0 |.
ร๐
Therefore, ๐งโ๐(๐) cost(๐ง) โค 2 ๐=2 |๐๐ | + 2|๐ 0 | โค 2๐(๐ฃ).
ร
4.2 Construction of the bad instance
We construct two instances: instance ๐ห on ๐ โ points, that is a semi-permutation (but is
somewhat easier to analyze), and instance ๐ โ in ๐ โ points, which is a permutation; the analysis
of instance ๐ โ heavily relies on the analysis of instance ๐. ห We will show that the optimal
solution value of both instances is ฮฉ(๐ log log ๐ ), but the cost of the Wilber Bound is at most
โ โ
๐(๐ โ log log log ๐ โ ). Our construction uses the following three parameters. We let โ โฅ 1 be an
integer, and we set ๐ = 2โ and ๐ = 2๐ .
4.2.1 First instance
ห which is a semi-permutation containing ๐ columns.
We now construct our first instance ๐,
Intuitively, we create ๐ instances ๐ , ๐ 1 , . . . , ๐ ๐โ1 , where instance ๐ ๐ is an exponentially-
0
spaced BRS instance that is shifted by ๐ units. We then stack these instances on top of one
another in this order.
Formally, for all 0 โค ๐ โค ๐ โ 1, we define a set โ ๐ of ๐ consecutive rows with integral coordinates,
such that the rows of โ 0 , โ 1 , . . . , โ ๐โ1 appear in this bottom-to-top order. Specifically, set โ ๐
contains all rows whose ๐ฆ-coordinates are in {๐๐ + 1, ๐๐ + 2, . . . , (๐ + 1)๐}.
For every integer 0 โค ๐ โค ๐ โ 1, we define a set of points ๐ ๐ , which is a cyclic shift of instance
ES-BRS(โ , โ ๐ ) by ๐ units. Recall that |๐ ๐ | = 2โ = ๐ and that the points in ๐ ๐ appear on the rows
in โ ๐ and a set ๐๐ of columns, whose ๐ฅ-coordinates are in { 2 ๐ + ๐ mod ๐ : 0 โค ๐ < ๐}. We
then let our final instance be ๐ห = ๐โ1 ๐ ห
๐ =0 ๐ . From now on, we denote ๐ = | ๐ |. Recall that
โ
ร
|๐ | = ๐ ยท ๐ = ๐ log ๐.
โ
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 28
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
Observe that the number of active columns in ๐ห is ๐. Since the instance is symmetric and
contains ๐ โ = ๐ log ๐ points, every column contains exactly log ๐ points. Each row contains
exactly one point, so ๐ห is a semi-permutation. (See Figure 5 for an illustration).
Figure 5: An illustration of our construction. The figure on the left shows the instance
BRS(2, [4], [4]). The figure on the right combines three copies ๐ 0 , ๐ 1 , ๐ 2 of the corresponding
exponentially-spaced instance, with horizontal shifts of 0, 1, and 2, respectively. The red points
are shifted copies of the same point in different sub-instances.
ห
Lastly, we need the following bound on the value of the optimal solution of instance ๐.
ห = ฮฉ(๐ โ log log ๐ โ )
Observation 4.6. OPT(๐)
Proof. From Claims 4.2 and 4.3, for each 0 โค ๐ โค ๐ โ 1, each sub-instance ๐ ๐ has OPT(๐ ๐ ) โฅ
ฮฉ(๐ log ๐) = ฮฉ(log ๐ log log ๐). Therefore, OPT(๐) ห โฅ ร๐โ1 OPT(๐ ๐ ) = ฮฉ(๐ log ๐ log log ๐) =
๐ =0
ฮฉ(๐ โ log log ๐ โ ) (we have used the fact that ๐ โ = ๐ log ๐).
4.2.2 Second instance
We now construct our second and final instance, ๐ โ , that is a permutation. In order to do so,
we start with the instance ๐,ห and, for every active column ๐ถ of ๐, ห we create ๐ = log ๐ new
columns (that we view as copies of ๐ถ), ๐ถ , . . . , ๐ถ
1 log ๐ , which replace the column ๐ถ. We denote
this set of columns by โฌ(๐ถ), and we refer it as the block of columns representing ๐ถ. Recall that
the original column ๐ถ contains log ๐ input points of ๐. ห We place each such input point on a
distinct column of โฌ(๐ถ), so that the points form a monotonically increasing sequence (see the
definition in Section 4.1). This completes the definition of the final instance ๐ โ . We obtain the
following immediate bound on the optimal solution cost of instance ๐ โ .
ห = ฮฉ(๐ โ log log ๐ โ ).
Claim 4.7. OPT(๐ โ ) โฅ OPT(๐)
Next, we proceed to prove the following theorem.
ห โค ๐(๐ โ log log log ๐ โ ).
Theorem 4.8. WB(๐)
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 29
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
ห Recall that it consists of ๐ instances ๐ 0 , ๐ 1 , . . . , ๐ ๐โ1 that are stacked
Recall again the instance ๐.
on top of each other vertically in this order. We rename these instances as ๐1 , ๐2 , . . . , ๐๐ , so ๐ ๐ is
exactly ES-BRS(log ๐), that is shifted by (๐ โ 1) units to the right. Recall that | ๐ห | = ๐ โ = ๐ log ๐,
and each instance ๐๐ contains exactly log ๐ points. We denote by ๐ the set of ๐ columns,
whose ๐ฅ-coordinates are 1, 2, . . . , ๐. All points of ๐ห lie on the columns of ๐. For convenience,
for 1 โค ๐ โค ๐, we denote by ๐ถ ๐ the column of ๐ whose ๐ฅ-coordinate is ๐.
Let ๐ be any ordering of the auxiliary columns in โ, and let ๐ = ๐(๐) be the corresponding
ห is
partitioning tree. It is enough to show that, for any such ordering ๐, the value of WB๐ (๐)
bounded by ๐(๐ log log log ๐ ).
โ โ
The total costs of the bound is divided into two parts as follows. Recall that ๐ ๐ต ๐ (๐) ห is the
sum, over all vertices ๐ฃ โ ๐(๐), of cost(๐ฃ). If ๐ฃ is a leaf vertex, then cost(๐ฃ) = 0. Otherwise,
let ๐ฟ = ๐ฟ(๐ฃ) be the line of โ that ๐ฃ owns. Index the points in ๐ โฉ ๐(๐ฃ) by ๐1 , . . . , ๐ ๐ง in their
bottom-to-top order. A consecutive pair (๐ ๐ , ๐ ๐+1 ) of points is a crossing iff they lie on different
sides of ๐ฟ(๐ฃ). We distinguish between the two types of crossings that contribute towards cost(๐ฃ).
We say that the crossing (๐ ๐ , ๐ ๐+1 ) is of type-1 if both ๐ ๐ and ๐ ๐+1 belong to the same shifted
instance ๐๐ for some 0 โค ๐ โค ๐ โ 1. Otherwise, they are of type-2. Note that, if (๐ ๐ , ๐ ๐+1 ) is a
crossing of type 2, with ๐ ๐ โ ๐๐ and ๐ ๐+1 โ ๐๐ 0 , then ๐ , ๐ 0 are not necessarily consecutive integers,
as it is possible that for some indices ๐ 00, ๐๐ 00 has no points that lie in the strip ๐(๐ฃ). We now let
cost1 (๐ฃ) be the total number of type-1 crossings of ๐ฟ(๐ฃ), and cost2 (๐ฃ) the total number of type-2
ร
crossings. Note that cost(๐ฃ) = cost1 (๐ฃ) + cost2 (๐ฃ). We also define cost1 (๐) = ๐ฃโ๐(๐) cost1 (๐ฃ) and
cost2 (๐) = ๐ฃโ๐(๐) cost2 (๐ฃ). Clearly, WB๐ (๐)
ร ห = cost1 (๐) + cost2 (๐). We prove the following two
theorems.
Theorem 4.9. For every ordering ๐ of the auxiliary columns in โ, cost1 (๐) โค ๐(๐ โ log log log ๐ โ ).
Theorem 4.10. For every vertex ๐ฃ โ ๐(๐), cost2 (๐ฃ) โค ๐(log ๐) + ๐(cost1 (๐ฃ)).
We prove these theorems in Section 4.3 and 4.4. The latter implies that cost2 (๐) โค ๐(cost1 (๐)) +
๐(|๐(๐)| ยท log ๐) = ๐(๐ โ log log log ๐ โ ) + ๐(๐ log ๐) = ๐(๐ โ log log log ๐ โ ). Combining the
two theorems together completes the proof of Theorem 4.8.
4.2.3 Upper bounding WB(๐ โ )
We argue that WB(๐ โ ) = ๐(๐ โ log log log ๐ โ ), completing the proof of Theorem 1.1. Recall that
instance ๐ โ is obtained from instance ๐ห by replacing every active column ๐ถ of ๐ โ with a block
โฌ(๐ถ) of columns, and then placing the points of ๐ถ on the columns of โฌ(๐ถ) so that they form a
monotone increasing sequence, while preserving their ๐ฆ-coordinates. The resulting collection
of all blocks โฌ(๐ถ) partitions the set of all active columns of ๐ โ . We denote this set of blocks by
โฌ1 , . . . , โฌ๐ . The idea is to use Theorem 3.6 in order to bound WB(๐ โ ).
Consider a set of lines โ 0 (with half-integral ๐ฅ-coordinates) that partition the bounding box
๐ต into ๐ strips, where the ๐th strip contains the block โฌ๐ of columns, so |โ 0 | = (๐ โ 1). We
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 30
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
consider a split of instance ๐ โ by โ 0: This gives us a collection of strip instances ๐๐โ 1โค๐โค๐ and
the compressed instance ๐ eโ . Notice that the compressed instance is precisely ๐, ห and each strip
instance ๐๐ is a monotone increasing point set.
โ
Since each strip instance ๐๐โ is monotonously increasing, from Observation 4.1 and Claim 2.7,
for all ๐, WB(๐๐โ ) โค ๐(OPT(๐๐โ )) โค ๐(|๐๐โ |). From Theorem 3.6, we then get that: WB(๐ โ ) โค
4WB(๐) ห + 8 ร๐ WB(๐ โ ) + ๐(|๐ โ |) โค 4WB(๐)
ห + ๐(|๐ โ |) โค ๐(๐ โ log log log ๐ โ ).
๐
4.3 Bounding type-1 crossings
The goal of this subsection is to prove Theorem 4.9.
We prove this theorem by a probabilistic argument. Consider the following experiment. Fix the
permutation ๐ of โ. Pick an integer ๐ โ {0, . . . , ๐ โ 1} uniformly at random, and let ๐ be the
resulting instance ๐๐ . This random process generates an input ๐ containing ๐ = log ๐ points.
Equivalently, let ๐ 1 , ๐2 , . . . , ๐ log ๐ be the points in BRS(โ ) ordered from left to right. Once we
choose a random shift ๐ , we move these points to columns in ๐๐ = {2 ๐ + ๐ mod ๐ }, where
point ๐ ๐ would be moved to ๐ฅ-coordinate 2 ๐ + ๐ mod ๐. Therefore, in the analysis, we view the
location of points ๐ 1 , . . . , ๐ log ๐ as random variables.
We denote by ๐(๐) the expected value of WB๐ (๐), over the choices of the shift ๐ . The following
observation is immediate, and follows from the fact that the final instance ๐ห contains every
instance ๐๐ for all shifts ๐ โ {0, . . . , ๐ โ 1}.
Observation 4.11. cost1 (๐) = ๐ ยท ๐(๐)
Therefore, in order to prove Theorem 4.9, it is sufficient to show that, for every fixed permutation
๐ of โ, ๐(๐) โค ๐(log ๐ log log log ๐) (recall that ๐ โ = ๐ log ๐).
We assume from now on that the permutation ๐ (and the corresponding partitioning tree ๐) is
fixed, and we analyze the expectation ๐(๐). Let ๐ฃ โ ๐(๐). We say that ๐(๐ฃ) is a seam strip iff point
๐ 1 lies in the strip ๐(๐ฃ). We say that ๐(๐ฃ) is a bad strip (or that ๐ฃ is a bad node) if the following
two conditions hold: (i) ๐(๐ฃ) is not a seam strip; and (ii) ๐(๐ฃ) contains at least 100 log log ๐
points of ๐. Let โฐ(๐ฃ) be the bad event that ๐(๐ฃ) is a bad strip.
Claim 4.12. For every vertex ๐ฃ โ ๐(๐), Pr [โฐ(๐ฃ)] โค 8 width(๐(๐ฃ)) .
๐ log
100
๐
Proof. Fix a vertex ๐ฃ โ ๐(๐). For convenience, we denote ๐(๐ฃ) by ๐. Let ๐ be the random integer
chosen by the algorithm and let ๐๐ = ๐ be the resulting point set. Assume that ๐ is a bad strip,
and let ๐ฟ be the vertical line that serves as the left boundary of ๐. Let ๐ ๐ be the point of ๐๐ that
lies to the left of ๐ฟ, and among all such points, we take the one closest to ๐ฟ. Recall that for each
1 โค ๐ < log ๐, there are 2 ๐ โ 1 columns of ๐ that lie between the column of ๐ ๐ and the column of
๐ ๐+1 .
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 31
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
If ๐ is a bad strip, then it must contain points ๐ ๐+1 , ๐ ๐+2 , . . . , ๐ ๐+๐ , where ๐ = 100 log log ๐.
Therefore, the number of columns of ๐ in strip ๐ is at least 2 ๐+๐โ2 , or, equivalently, width(๐) โฅ
2 ๐+๐ /4 โฅ (2 ๐ log100 ๐)/4. In particular, 2 ๐ โค 4 width(๐)/log100 ๐.
Therefore, in order for ๐ to be a bad strip, the shift ๐ must be chosen in such a way that the point
๐ ๐ , that is the rightmost point of ๐๐ lying to the left of ๐ฟ, has 2 ๐ โค 4 width(๐)/log100 ๐. It is easy
to verify that the total number of all such shifts ๐ is bounded by 8 width(๐)/log100 ๐.
In order to see this, consider an equivalent experiment, in which we keep the instance ๐1
fixed, and instead choose a random shift ๐ โ {0, . . . , ๐ โ 1} for the line ๐ฟ. For the bad event
โฐ(๐ฃ) to happen, the line ๐ฟ must fall in the interval between ๐ฅ-coordinate 0 and ๐ฅ-coordinate
8 width(๐)/log100 ๐. Since every integral shift ๐ is chosen with the same probability 1/๐, the
probability that โฐ(๐ฃ) happens is at most 8 width(๐) .
๐ log
100
๐
Consider now the partitioning tree ๐. We partition the vertices of ๐ into log ๐ + 1 classes
๐ 1 , . . . , ๐ log ๐+1 . A vertex ๐ฃ โ ๐(๐) lies in class ๐ ๐ iff 2๐ โค width(๐(๐ฃ)) < 2๐+1 . Therefore, every
vertex of ๐ belongs to exactly one class.
Consider now some vertex ๐ฃ โ ๐(๐), and assume that it lies in class ๐ ๐ . We say that ๐ฃ is an
important vertex for class ๐ ๐ iff no ancestor of ๐ฃ in the tree ๐ belongs to class ๐ ๐ . Notice that, if ๐ข
is an ancestor of ๐ฃ, and ๐ข โ ๐ ๐ , then ๐ โฅ ๐ must hold.
For each 1 โค ๐ โค log ๐ + 1, let ๐ ๐ be the set of all important vertices of class ๐ ๐ .
Observation 4.13. For each 1 โค ๐ โค log ๐ + 1, |๐ ๐ | โค ๐/2๐ .
Proof. Since no vertex of ๐ ๐ may be an ancestor of another vertex, the strips in {๐(๐ฃ) | ๐ฃ โ ๐ ๐ }
are mutually disjoint, except for possibly sharing their boundaries. Since each strip has width at
least 2๐ , and we have exactly ๐ columns, the number of such strips is bounded by ๐/2๐ .
Let โฐ be the bad event that there is some index 1 โค ๐ โค log ๐ + 1, and some important vertex
๐ฃ โ ๐ ๐ of class ๐ ๐ , for which the event โฐ(๐ฃ) happens. Applying the Union Bound to all strips in
{๐(๐ฃ) | ๐ฃ โ ๐ ๐ } and all indices 1 โค ๐ โค log ๐, we obtain the following corollary of Claim 4.12.
Corollary 4.14. Pr [โฐ] โค 32
.
log99 ๐
Proof. Fix some index 1 โค ๐ โค log ๐. Recall that for every important vertex ๐ฃ โ ๐ ๐ , the
๐+1 ๐
probability that the event โฐ(๐ฃ) happens is at most 8 width(๐(๐ฃ)) โค 8ยท2 100 = 16ยท2100 . From
100
๐ log ๐ ๐ log ๐ ๐ log ๐
Observation 4.13, |๐ ๐ | โค ๐/2๐ . From the union bound, the probability that event โฐ(๐ฃ) happens
for any ๐ฃ โ ๐ ๐ is bounded by 16 . Using the union bound over all 1 โค ๐ โค log ๐ + 1, we
100
log ๐
conclude that Pr [โฐ] โค 32
.
log99 ๐
Lastly, we show that, if event โฐ does not happen, then the cost of the Wilber Bound is sufficiently
small.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 32
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
Lemma 4.15. Let 1 โค ๐ โค ๐ be a shift for which โฐ does not happen. Then:
๐ ๐ต ๐ (๐๐ ) โค ๐(log ๐ log log log ๐).
Proof. Consider the partitioning tree ๐ = ๐(๐). We say that a vertex ๐ฃ โ ๐(๐) is a seam vertex iff
๐(๐ฃ) is a seam strip, that is, the point ๐ 1 in instance ๐๐ lies in ๐(๐ฃ). Clearly, the root of ๐ is a
seam vertex, and for every seam vertex ๐ฃ, exactly one of its children is a seam vertex. Therefore,
there is a root-to-leaf path ๐ that only consists of seam vertices, and every seam vertex lies on
๐. We denote the vertices of ๐ by ๐ฃ 1 , ๐ฃ2 , . . . , ๐ฃ ๐ , where ๐ฃ 1 is the root of ๐, and ๐ฃ ๐ is a leaf. For
1 < ๐ โค ๐, we denote by ๐ฃ 0๐ the sibling of the vertex ๐ฃ ๐ . Note that all strips ๐(๐ฃ 20 ), . . . , ๐(๐ฃ 0๐ ) are
ร๐
mutually disjoint, except for possibly sharing boundaries, and so ๐=2 ๐(๐ฃ 0๐ ) โค |๐๐ | = log ๐.
ร๐
Moreover, from Claim 4.5, ๐=1 cost(๐ฃ ๐ ) โค 2|๐๐ | = 2 log ๐.
For each 1 < ๐ โค ๐, let ๐๐ be the subtree of ๐ rooted at the vertex ๐ฃ 0๐ . We prove the following
claim:
Claim 4.16. For all 1 < ๐ โค ๐, the total cost of all vertices in ๐๐ is at most ๐(๐(๐ฃ 0๐ ) log log log ๐).
Assume first that the above claim is correct. Notice that every vertex of ๐ that does not lie on
the path ๐ must belong to one of the trees ๐๐ . The total cost of all vertices lying in all trees ๐๐
ร๐
is then bounded by ๐=2 ๐(๐(๐ฃ 0๐ ) log log log ๐) โค ๐(log ๐ log log log ๐). Since the total cost
of all vertices on the path ๐ is bounded by 2 log ๐, overall, the total cost of all vertices in ๐ is
bounded by ๐(log ๐ log log log ๐).
In order to complete the proof of Lemma 4.15, it now remains to prove Claim 4.16.
Proof. Claim 4.16 We fix some index 1 < ๐ โค ๐, and consider the vertex ๐ฃ 0๐ . If the parent ๐ฃ ๐โ1 of ๐ฃ 0๐
belongs to a different class than ๐ฃ 0๐ , then ๐ฃ 0๐ must be an important vertex in its class. In this case,
since we have assumed that Event โฐ does not happen, ๐(๐ฃ 0๐ ) โค ๐(log log ๐). From Claim 4.5,
the total cost of all vertices in ๐๐ is bounded by
ร
cost(๐ฃ) โค ๐(๐(๐ฃ 0๐ ) log(๐(๐ฃ 0๐ ))) โค ๐(๐(๐ฃ 0๐ ) log log log ๐)
๐ฃโ๐(๐๐ )
Therefore, we can assume from now on that ๐ฃ ๐โ1 and ๐ฃ 0๐ both belong to the same class, that we
denote by ๐ ๐ . Notice that, if a vertex ๐ฃ belongs to class ๐ ๐ , then at most one of its children may
belong to class ๐ ๐ ; the other child must belong to some class ๐ ๐0 for ๐ 0 < ๐, and it must be an
important vertex in its class.
We now construct a path ๐๐ in tree ๐๐ iteratively, as follows. The first vertex on the path is ๐ฃ 0๐ .
We then iteratively add vertices at to the end of path ๐๐ one-by-one, so that every added vertex
belongs to class ๐ ๐ . In order to do so, let ๐ฃ be the last vertex on the current path ๐๐ . If some
child ๐ข of ๐ฃ also lies in class ๐ ๐ , then we add ๐ข to the end of ๐๐ and continue to the next iteration.
Otherwise, we terminate the construction of the path ๐๐ .
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 33
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
Denote the sequence of vertices on the final path ๐๐ by (๐ฃ 0๐ = ๐ข1 , ๐ข2 , . . . , ๐ข๐ง ); recall that every
vertex on ๐๐ belongs to class ๐ ๐ , and that path ๐๐ is a sub-path of some path connecting ๐ฃ 0๐
to a leaf of ๐๐ . Let ๐ be a set of vertices containing, for all 1 < ๐ง 0 โค ๐ง a sibling of the vertex
๐ข๐ง0 , and additionally the two children of ๐ข๐ง (if they exist). Note that every vertex ๐ฅ โ ๐ is
an important vertex in its class, and, since we have assumed that Event โฐ did not happen,
๐(๐ฅ) โค ๐(log log ๐). For every vertex ๐ฅ โ ๐, we denote by ๐๐ฅ0 the subtree of ๐ rooted at ๐ฅ. From
Claim 4.5, cost(๐๐ฅ0 ) โค ๐(๐(๐ฅ) log(๐(๐ฅ))) = ๐(๐(๐ฅ) log log log ๐).
Notice that all strips in {๐(๐ฅ) | ๐ฅ โ ๐} are disjoint from each other, except for possibly sharing a
boundary. It is then easy to see that ๐ฅโ๐ ๐(๐ฅ) โค ๐(๐ฃ 0๐ ). Therefore, altogether ๐ฅโ๐ cost(๐๐ฅ0 ) โค
ร ร
๐(๐(๐ฃ 0๐ ) log log log ๐)).
Lastly, notice that every vertex of ๐(๐๐ ) either lies on ๐๐ , or belongs to one of the trees ๐๐ฅ0 for
๐ฅ โ ๐. Since, from Claim 4.5, the total cost of all vertices on ๐๐ is bounded by ๐(๐ฃ 0๐ ), altogether,
the total cost of all vertices in ๐๐ is bounded by ๐(๐(๐ฃ 0๐ ) log log log ๐)).
To summarize, if the shift ๐ is chosen such that Event โฐ does not happen, ๐ ๐ต ๐ (๐๐ ) โค
๐(log ๐ log log log ๐). Assume now that the shift ๐ is chosen such that Event โฐ happens.
From Corollary 4.14, the probability of this is at most Pr [โฐ] โค 32 . Since |๐๐ | = log ๐,
99
log ๐
from Corollary 4.4, WB๐ (๐๐ ) โค |๐๐ | log(|๐๐ |) โค log ๐ log log ๐. Therefore, altogether, we
get that ๐(๐) โค ๐(log ๐ log log log ๐), and cost1 (๐) = ๐ ยท ๐(๐) = ๐(๐ log ๐ log log log ๐) =
๐(๐ โ log log log ๐ โ ), as ๐ โ = ๐ log ๐.
4.4 Bounding type-2 crossings
This subsection is dedicated to the proof of Theorem 4.10. We fix a vertex ๐ฃ โ ๐(๐), and we
denote ๐ = ๐(๐ฃ). We also let ๐ฟ = ๐ฟ(๐ฃ) be the vertical line that ๐ฃ owns. Our goal is to show that
the number of type-2 crossings of ๐ฟ is bounded by ๐(cost1 (๐ฃ)) + ๐(log ๐).
Recall that instances ๐1 , . . . , ๐๐ are stacked on top of each other, so that the first log ๐ rows
with integral coordinates belong to ๐1 , the next log ๐ rows belong to ๐2 , and so on. If we have
a crossing (๐, ๐ 0), where ๐ โ ๐๐ and ๐ 0 โ ๐๐ 0 , then we say that the instances ๐๐ and ๐๐ 0 are
responsible for this crossings. Recall that ๐, ๐ 0 may only define a crossing if they lie on opposite
sides of the line ๐ฟ, and if no point of ๐ห lies in the strip ๐ between the row of ๐ and the row of ๐ 0.
It is then clear that every instance ๐๐ may be responsible for at most two type-2 crossings of ๐ฟ:
one in which the second instance ๐๐ 0 responsible for the crossing has ๐ 0 < ๐ , and one in which
๐ 0 > ๐ .
We further partition the type-2 crossings into two sub-types. Consider a crossing (๐, ๐ 0), and let
๐๐ , ๐๐ 0 be the two instances that are responsible for it. If either of ๐๐ , ๐๐ 0 contributes a type-1
crossing to the cost of ๐ฟ, then we say that (๐, ๐ 0) is a type-(2a) crossing; otherwise it is a type-(2b)
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 34
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
crossing. Clearly, the total number of type-(2a) crossings is bounded by ๐(cost1 (๐ฃ)). It is now
sufficient to show that the total number of all type-(2b) crossings is bounded by ๐(log ๐).
Consider now some type-(2b) crossing (๐, ๐ 0), and let ๐๐ and ๐๐ 0 be the two instances that are
responsible for it, with ๐ โ ๐๐ . We assume that ๐ < ๐ 0. Since neither instance contributes a
crossing to cost1 (๐ฃ), it must be the case that all points of ๐๐ โฉ ๐ lie to the left of ๐ฟ and all points
of ๐๐ 0 โฉ ๐ lie to the right of ๐ฟ or vice versa. Moreover, if ๐ 0 > ๐ + 1, then for all ๐ < ๐ 00 < ๐ 0,
๐๐ 00 โฉ ๐ = โ
.
It would be convenient for us to collapse each of the instances ๐1 , . . . , ๐๐ into a single row. In
order to do so, for each 1 โค ๐ โค ๐, we replace all rows on which the points of ๐๐ lie with a single
row ๐
๐ . If some point of ๐๐ lies on some column ๐ถ, then we add a point at the intersection of ๐
๐
and ๐ถ.
We say that a row ๐
๐ is empty if there are no input points in ๐
๐ โฉ ๐. We say that it is a neutral
row, if there are points in ๐
๐ โฉ ๐ both to the left of ๐ฟ and to the right of ๐ฟ. We say that it is a left
row if ๐
๐ โฉ ๐ only contains points lying to the left of ๐ฟ, and we say that it is a right row if ๐
๐ โฉ ๐
only contains points lying to the right of ๐ฟ.
If we now consider any type-(2b) crossing (๐, ๐ 0), and the instances ๐๐ , ๐๐ 0 that are responsible
for it, with ๐ < ๐ 0, then it must be the case that exactly one of the rows ๐
๐ , ๐
๐ 0 is a left row, and
the other is a right row. Moreover, if ๐ 0 > ๐ + 1, then every row lying between ๐
๐ and ๐
๐ 0 is an
empty row.
Let us denote the points in ๐1 by ๐ 1 , . . . , ๐ log ๐ , where for each 1 โค ๐ โค log ๐, point ๐ ๐ lies in
column ๐ถ2๐ . In each subsequent instance ๐2 , ๐3 , . . ., the point is shifted by one unit to the right,
so that in instance ๐๐ it lies in column ๐ถ2๐ +๐ โ1 ; every column in ๐ must contain exactly one copy
of point ๐ ๐ .
Consider now all copies of the point ๐ ๐ that lie in the strip ๐. Let โ ๐ be the set of rows containing
these copies. Then two cases are possible: either (i) โ ๐ is a contiguous set of rows, and the
copies of ๐ ๐ appear on โ ๐ diagonally as an increasing sequence (the ๐th row of โ ๐ contains a
copy of ๐ ๐ that lies in the ๐th column of ๐ in the strip ๐); or โ ๐ consists of two consecutive sets of
rows; the first set, that we denote by โ 0๐ , contains ๐
1 , and the second set, that we denote by โ 00๐ ,
contains the last row ๐
๐ . The copies of the point ๐ ๐ also appear diagonally in โ 0๐ and in โ 00๐ ; in
โ 00๐ the first copy lies on the first column of ๐ in ๐; in โ 0๐ the last copy lies on the last column of
๐ in ๐ (see Figure 6).
We show that for each 1 โค ๐ โค log ๐, there are at most four type-(2b) crossings of the line ๐ฟ in
which a copy of ๐ ๐ participates. Indeed, consider any type-(2b) crossing (๐, ๐ 0) in which a copy
of ๐ ๐ participates. We assume that the row of ๐ lies below the row of ๐ 0. Assume first that both
๐ and ๐ 0 lie on rows of โ ๐ , and let ๐
, ๐
0 be these two rows, with ๐ โ ๐
, ๐ 0 โ ๐
0. Recall that, in
order for (๐, ๐ 0) to define a crossing, all input points that lie on ๐
โฉ ๐ must lie to the left of ๐ฟ,
and all point points that lie on ๐
0 โฉ ๐ must lie to the right of ๐ฟ, or the other way around. It is
easy to verify (see Figure 6) that one of two cases must happen: either ๐
contains a copy of ๐ ๐
lying closest to ๐ฟ on its left, and ๐
0 contains a copy of ๐ ๐ lying closest to ๐ฟ on its right; or ๐
is the
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 35
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
L L
(b) The two consecutive sets of rows on
(a) The consecutive set of rows on which which the copies of ๐ ๐ appear are โ 0๐ (on
the copies of ๐ ๐ appear is denoted by โ ๐ . the bottom) and โ 00๐ (on the top).
Figure 6: Two patterns in which copies of ๐ ๐ may appear on strip ๐.
last row of โ 0๐ , and ๐
0 is the first row of โ 00๐ . Therefore, only two such crossing, with ๐
, ๐
0 โ โ ๐
are possible.
Assume now that ๐
โ โ ๐ and ๐
0 โ โ ๐ ; recall that we assume that ๐
0 lies above ๐
. Then all rows
that lie between ๐
and ๐
0 must be empty, so it is easy to verify that ๐
must be the last row of โ ๐
(or it must be the last row of โ 0๐ ). In either case, at most one such crossing is possible.
Lastly, we assume that ๐
โ โ ๐ and ๐
0 โ โ ๐ . The analysis is symmetric; it is easy to see that at
most one such crossing is possible.
We conclude that for each 1 โค ๐ โค log ๐, at most four type-(2b) crossings of the line ๐ฟ may
involve copies of ๐ ๐ , and so the total number of type-(2b) crossings of ๐ฟ is bounded by ๐(log ๐).
To summarize, we have shown that for every ordering ๐ of the auxiliary columns in โ,
ห = ๐(๐ โ log log log ๐ โ ). Since OPT(๐)
cost1 (๐), cost2 (๐) โค ๐(๐ โ log log log ๐ โ ), and so WB๐ (๐) ห =
โ โ โ โ ห
ฮฉ(๐ log log ๐ ), we obtain a gap of ฮฉ(log log ๐ /log log log ๐ ) between OPT(๐) and WB(๐). ห
4.5 Separating WB(2) and WB
log log ๐
In this section, we extend our ฮฉ( log log log ๐ )-factor separation between WB and OPT to a separation
between WB and the second Wilber bound (denoted by WB(2) ), which is defined below.4
4Wilber originally defined this bound based on the tree view. We use an equivalent geometric definition as
discussed in [11, 18].
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 36
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
Let ๐ be a set of ๐ points that is a semi-permutation. Consider any point ๐ โ ๐. The funnel of
๐, denoted by funnel(๐ , ๐) is the set of all points ๐ โ ๐, such that ๐, ๐ฆ < ๐.๐ฆ, and ๐,๐ contains
no point of ๐ \ {๐, ๐}. Denote funnel(๐ , ๐) = {๐ 1 , ๐2 , . . . , ๐ ๐ }, where the points are indexed in
the increasing order of their ๐ฆ-coordinates. Let alt(๐ , ๐) be the number of indices 1 โค ๐ < ๐,
such that ๐ ๐ lies strictly to the left of ๐ and ๐ ๐+1 lies strictly to the right of ๐, or the other way
around. The second Wilber bound is:
ร
WB(2) (๐) = ๐ + alt(๐ , ๐).
๐โ๐
The goal of this section is to prove the following:
Theorem 4.17. For infinitely many integer ๐, there exists a point set ๐ that is a permutation with
|๐ | = ๐, such that WB(2) (๐) โฅ ฮฉ(๐ log log ๐) but WB(๐) โค ๐(๐ log log log ๐).
As it is known that OPT(๐) โฅ WB(2) (๐) for any point set ๐ [29], Theorem 4.17 is a stronger
statement than Theorem 1.1. To prove Theorem 4.17, we use exactly the same permutation
sequence ๐ โ of size ๐ โ that is constructed in Section 4.2. Since we already showed that
WB(๐ โ ) โค ๐(๐ โ log log log ๐ โ ), it remains to show that WB(2) (๐ โ ) โฅ ฮฉ(๐ โ log log ๐ โ ).
We use the following claim of Wilber [29].
Claim 4.18 ([29]). WB(2) (BRS(๐)) = ฮฉ(๐ log ๐) for any ๐.
We extend this bound to the cyclically shifted BRS in the following lemma.
Lemma 4.19. For integers ๐ > 0, ๐ with 0 โค ๐ < ๐, let ๐ be the sequence obtained by performing a
cyclic shift to BRS(๐) by ๐ units. Then WB(2) (๐) = ฮฉ(๐ log ๐).
Proof. Observe that, for any choice of ๐ , there must exists a subsequence ๐ 0 of ๐ such that ๐ 0 is
a copy of BRS(๐ โ 1). It is shown in Lemma 6.2 of [22] that for any pair of sequences ๐, ๐0 with
๐0 โ ๐, WB(2) (๐0) โค WB(2) (๐) holds. Therefore, we conclude that
WB(2) (๐) โฅ WB(2) (BRS(๐ โ 1)) โฅ ฮฉ(๐ log ๐).
Now, we are ready to bound WB(2) (๐ โ ).
Lemma 4.20. WB(2) (๐ โ ) = ฮฉ(๐ โ log log ๐ โ ).
Proof. Recall that ๐ห is the union of the sets ๐ 0 , ๐ 1 , . . . , ๐ ๐โ1 of points, where for all 0 โค ๐ โค ๐ โ1,
set ๐ ๐ is an exponentially-spaced BRS instance that is shifted by ๐ units. From the definition
ห โฅ ร๐โ1 WB(2) (๐ ๐ ). This is since, for all 0 โค ๐ โค ๐ โ 1,
of WB(2) , it is easy to see that WB(2) (๐) ๐ =0
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 37
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
for ever point ๐ โ ๐ ๐ , funnel(๐ ๐ , ๐) โ funnel(๐ห , ๐), and moreover alt(๐ห , ๐) โฅ alt(๐ ๐ , ๐). From
Lemma 4.19, we get that WB(2) (๐ ๐ ) = ฮฉ(๐ log ๐), where ๐ = |๐ ๐ | = log ๐. Therefore,
ห โฅ ๐ ยท ฮฉ(๐ log ๐) = ฮฉ(๐ โ log log ๐ โ ).
WB(2) (๐)
Finally, recall that the sequence ๐ โ is obtained from ๐ห by replacing each column ๐ถ of ๐ห with
a block โฌ(๐ถ) of columns, and placing all points of ๐ห lying in ๐ถ on the columns of โฌ(๐ถ) so
that they form a monotonically increasing sequence of length ๐. It is not hard to see that
ห which concludes the proof.
WB(2) (๐ โ ) โฅ WB(2) (๐)
5 Guillotine bounds
In this section we define two extensions of the strong Wilber bound and extend our negative
results to one of these bounds. In subSection 5.1, we provide formal definitions of these bounds,
and we present our negative result in subsequent subsections.
5.1 Definitions
Assume that we are given an input set ๐ of ๐ points, that is a permutation. Let โ ๐ be the set of
all vertical lines with half-integral ๐ฅ-coordinates between 1/2 and ๐ โ 1/2, and let โ ๐ป be the
set of all horizontal lines with half-integral ๐ฆ-coordinates between 1/2 and ๐ โ 1/2. Recall that
for every permutation ๐ of โ ๐ , we have defined a bound WB๐ (๐). We can similarly define a
bound WB0๐0 (๐) for every permutation ๐0 of โ ๐ป . We also let WB0(๐) be the maximum, over
all permutations ๐0 of โ ๐ป , of WB0๐0 (๐). Equivalently, let ๐ 0 be an instance obtained from ๐ by
rotating it by 90 degrees clockwise. Then WB0(๐) = WB(๐ 0). We denote by ๐ต a bounding box
that contains all points of ๐.
5.1.1 Consistent Guillotine Bound
In this section we define the consistent Guillotine Bound, cGB(๐). Let ๐ be any permutations of
all lines in โ ๐ โช โ ๐ป . We start from a bounding box ๐ต containing all points of ๐ and maintain a
partition ๐ซ of the plane into rectangular regions, where initially ๐ซ = {๐ต}. We process the lines
in โ ๐ โช โ ๐ป according to their ordering in ๐. Consider an iteration when a line ๐ฟ is processed.
Let ๐1 , . . . , ๐๐ be all rectangular regions in ๐ซ that intersect the line ๐ฟ. For each such region ๐ ๐ ,
let ๐ 0๐ and ๐ 00๐ be the two rectangular regions into which the line ๐ฟ splits ๐ ๐ . We update ๐ซ by
replacing each region ๐ ๐ , for 1 โค ๐ โค ๐, with the regions ๐ 0๐ and ๐ 00๐ . Once all lines in โ ๐ โช โ ๐ป
are processed, we terminate the process.
This recursive partitioning procedure can be naturally associated with a partitioning tree ๐ = ๐๐
that is defined as follows:
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 38
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
โข Each vertex ๐ฃ โ ๐(๐) is associated with a rectangular region ๐(๐ฃ) of the plane. If ๐ is the
root of ๐, then ๐(๐) = ๐ต.
โข Each non-leaf vertex ๐ฃ is associated with a line ๐ฟ(๐ฃ) โ โ ๐ป โช โ ๐ that was used to partition
๐(๐ฃ) into two sub-regions, ๐0 and ๐00. Vertex ๐ฃ has two children ๐ฃ 1 , ๐ฃ2 in ๐, with ๐(๐ฃ 1 ) = ๐0
and ๐(๐ฃ 2 ) = ๐00.
โข For each leaf node ๐ฃ, the region ๐(๐ฃ) contains at most one point of ๐.
We now define the cost cost(๐ฃ) of each node ๐ฃ โ ๐(๐). If the region ๐(๐ฃ) contains no points
of ๐, or it contains a single point of ๐, then cost(๐ฃ) = 0. Otherwise, we define cost(๐ฃ) in the
same manner as before. Assume first that the line ๐ฟ(๐ฃ) is vertical. Let ๐ 1 , . . . , ๐ ๐ be all points in
๐ โฉ ๐(๐ฃ), indexed in the increasing order of their ๐ฆ-coordinates. A pair (๐ ๐ , ๐ ๐+1 ) of consecutive
points forms a crossing of ๐ฟ(๐ฃ) for ๐(๐ฃ), if they lie on the opposite sides of ๐ฟ(๐ฃ). We then let
cost(๐ฃ) be the number of such crossings.
When ๐ฟ(๐ฃ) is a horizontal line, cost(๐ฃ) is defined analogously: we index the points of ๐ โฉ ๐(๐ฃ) in
the increasing order of their ๐ฅ-coordinates. We then say that a consecutive pair of such points is
a crossing iff they lie on opposite sides of ๐ฟ(๐ฃ). We let cost(๐ฃ) be the number of such crossings.
For a fixed ordering ๐ of the lines in โ ๐ โช โ ๐ป , and the corresponding partition tree ๐ = ๐(๐),
ร
we define cGB๐ (๐) = ๐ฃโ๐(๐) cost(๐ฃ).
Lastly, we define the consistent Guillotine Bound for a point set ๐ that is a permutation to be
the maximum, over all orderings ๐ of the lines in โ ๐ โช โ ๐ป , of cGB๐ (๐).
In the following subsection we define an even stronger bound, that we call the Guillotine bound,
and we show that for every point set ๐ that is a permutation, cGB(๐) โค GB(๐), and moreover
that GB(๐) โค ๐(OPT(๐)). It then follows that for every point set ๐ that is a permutation,
cGB(๐) โค ๐(OPT(๐)).
Theorem 5.1. For every integer ๐ 0, there is an integer ๐ โฅ ๐ 0, and a set ๐ of points that is a permutation
with |๐ | = ๐, such that OPT(๐) โฅ ฮฉ(๐ log log ๐) but cGB(๐) โค ๐(๐ log log log ๐).
The following lemma will be helpful in the proof of Theorem 5.1; recall that WB0(๐) is the basic
Wilber Bound, where we cut via horizontal lines only.
Lemma 5.2. For every instance ๐ that is a permutation, cGB(๐) โค WB(๐) + WB0(๐).
Proof. Let ๐ be a permutation of โ ๐ โช โ ๐ป , such that cGB(๐) = cGB๐ (๐). Notice that ๐
naturally induces a permutation ๐0 of โ ๐ and a permutation ๐00 of โ ๐ป . We show that
cGB๐ (๐) โค WB๐0 (๐) + WB0๐00 (๐). In order to do so, it is enough to show that for every vertical
line ๐ฟ โ โ ๐ , the cost that is charged to ๐ฟ in the bound cGB๐ (๐) is less than or equal to the cost
that is charged to ๐ฟ in the bound WB๐0 (๐), and similarly, for every horizontal line ๐ฟ0 โ โ ๐ป , the
cost that is charged to ๐ฟ0 in the bound cGB๐ (๐) is less than or equal to the cost that is charged to
๐ฟ0 in the bound WB0๐00 (๐). We show the former; the proof of the latter is similar.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 39
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
Consider any line ๐ฟ โ โ ๐ . We let ๐ be the partitioning tree associated with cGB๐ (๐), just before
line ๐ฟ is processed, and we let ๐ 0 be defined similarly for WB๐0 (๐). Let ๐ฃ โ ๐(๐ 0) be the leaf
vertex with ๐ฟ โ ๐(๐ฃ), and let ๐ be the set of all leaf vertices ๐ข of the tree ๐ with ๐(๐ข) โฉ ๐ฟ โ โ
.
Observe that the set of vertical lines that appear before ๐ฟ in ๐ and ๐0 is identical. Therefore,
๐(๐ฃ) = ๐ขโ๐ ๐(๐ข). It is easy to verify that, for every vertex ๐ข โ ๐, every crossing that contributes
ร
to cost(๐ข) is also a crossing that is charged to the line ๐ฟ in the strip ๐(๐ฃ). Therefore, the total
number of crossings of line ๐ฟ in tree ๐ 0 that contribute to WB๐0 (๐) is greater than or equal to the
number of crossings of the line ๐ฟ that contribute to cGB๐ (๐).
To conclude, we get that cGB(๐) = cGB๐ (๐) โค WB๐0 (๐) + WB0๐00 (๐) โค WB(๐) + WB0(๐).
5.1.2 The Guillotine Bound
In this section, we define a second extension of Wilber Bound, that we call Guillotine Bound,
and denote by GB. The bound is more convenient to define using a partitioning tree instead of a
sequence of lines. Let ๐ be a point set which is a permutation.
We define a guillotine partition of a point set ๐, together with the corresponding partitioning
tree ๐. As before, every node ๐ฃ โ ๐(๐) of the partitioning tree ๐ is associated with a rectangular
region ๐(๐ฃ) of the plane. At the beginning, we add the root vertex ๐ to the tree ๐, and we let
๐(๐) = ๐ต, where ๐ต is the bounding box containing all points of ๐. We then iterate, as long as
some leaf vertex ๐ฃ of ๐ has ๐(๐ฃ) โฉ ๐ containing more than one point. In each iteration, we
select any such leaf vertex ๐ฃ, and we select an arbitrary vertical or horizontal line ๐ฟ(๐ฃ), that is
contained in ๐(๐ฃ), and partitions ๐(๐ฃ) into two rectangular regions, that we denote by ๐0 and ๐00,
such that ๐ โฉ ๐0 , ๐ โฉ ๐00 โ โ
. We then add two child vertices ๐ฃ 1 , ๐ฃ2 to ๐ฃ, and set ๐(๐ฃ 1 ) = ๐0 and
๐(๐ฃ2 ) = ๐00. Once every leaf vertex ๐ฃ has |๐(๐ฃ) โฉ ๐ | = 1, we terminate the process and obtain the
final partitioning tree ๐.
The cost cost(๐ฃ) of every vertex ๐ฃ โ ๐(๐) is calculated exactly as before. We then let GB๐ (๐) =
๐ฃโ๐(๐) cost(๐ฃ), and we let GB(๐) be the maximum, over all partitioning trees ๐, of GB๐ (๐).
ร
We note that the main difference between cGB(๐) and GB(๐) is that in cGB bound, the
partitioning lines must be chosen consistently across all regions: that is, we choose a vertical or
a horizontal line ๐ฟ that crosses the entire bounding box ๐ต, and then we partition every region
that intersects ๐ฟ by this line ๐ฟ. In contrast, in the GB bound, we can partition each region ๐(๐ฃ)
individually, and choose different partitioning lines for different regions. It is then easy to see
that GB is more general than cGB, and, in particular, for every point set ๐ that is a permutation,
cGB(๐) โค GB(๐).
Lastly, we show that GB is a lower bound on the optimal solution cost, in the following lemma.
Lemma 5.3. For any point set ๐ that is a permutation, GB(๐) โค 2OPT(๐).
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 40
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
5.2 Negative results for the Consistent Guillotine Bound
In this section we prove Theorem 5.1.
We use three main parameters. Let โ โฅ 1 be an integer, and let ๐ = 2โ and ๐ = 2๐ . As before, we
will first construct point set ๐ห that is not a permutation (in fact, it is not even a semi-permutation),
and then we will turn it into our final instance ๐ โ which is a permutation.
5.2.1 2D exponentially spaced bit reversal
We define the instance 2D-ES-BRS(โ ) to be a bit-reversal sequence BRS(โ , โ, ๐), where the sets
โ and ๐ of activerows and columns are defined as follows. Set ๐ contains all columns with
๐ฅ-coordinates in 2 ๐ | 1 โค ๐ โค ๐ , and similarly set โ contains all rows with ๐ฆ-coordinates in
๐
2 | 1 โค ๐ โค ๐ . Note that set ๐ contains ๐ points, whose ๐ฅ- and ๐ฆ-coordinates are integers
between 1 and ๐.
5.2.2 2D cyclic shifts
Next, we define the shifted and exponentially spaced instance, but this time we shift both
vertically and horizontally. We assume that we are given a horizontal shift 0 โค ๐ < ๐ and a
vertical shift 0 โค ๐ 0 < ๐. In order to construct the instance ๐ ๐ ,๐ , we start with the instance
0
๐ = 2D-ES-BRS(โ ), and then perform the following two operations. First, we perform a
horizontal shift by ๐ units as before, by moving the last ๐ columns with integral ๐ฅ-coordinates to
the beginning of the instance. Next, we perform a vertical shift, by moving the last ๐ 0 rows with
integral ๐ฆ-coordinates to the bottom of the instance. We let ๐ ๐ ,๐ denote the resulting instance.
0
By applying Claim 4.3 twice, once for the horizontal shift, and once for the vertical shift, we get
that OPT(๐ ๐ ,๐ ) โฅ OPT(๐) โ 2|๐ | โฅ ฮฉ(log ๐ log log ๐), since |๐ | = log ๐.
0
5.2.3 Instance ๐ห
Next, we construct an instance ๐, ห by combining the instances ๐ ๐ ,๐ 0 for 0 โค ๐ , ๐ 0 < ๐. In order
to do so, let ๐ห be a set of ๐ 2 columns, with integral ๐ฅ-coordinates 1, . . . , ๐ 2 . We partition ๐ห
into subsets ๐1 , ๐2 , . . . , ๐๐ , each of which contains ๐ consecutive columns, they appear in this
left-to-right order. We call each such set ๐๐ a super-column. We denote by ๐๐ ๐
the smallest vertical
strip containing all columns of ๐๐ .
Similarly, we let โฬ be a set of ๐ 2 rows, with integral ๐ฆ-coordinates 1, . . . , ๐ 2 . We partition
โฬ into subsets โ 1 , . . . , โ ๐ , each of which contains ๐ consecutive rows, such that โ 1 , . . . , โ ๐
appear in this bottom-to-top order. We call each such set โ ๐ a super-row. We denote by ๐ ๐๐ป the
smallest horizontal strip containing all rows of โ ๐ . For all 1 โค ๐, ๐ โค ๐, we let ๐ต(๐, ๐) be the
intersection of the horizontal strip ๐ ๐๐ป and the vertical strip ๐๐
๐
. We plant the instance ๐ (๐โ1),(๐โ1)
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 41
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
ห Let ๐ โ = | ๐ห | = ๐ 2 log ๐
into the box ๐ต(๐, ๐). This completes the construction of instance ๐.
(recall that each instance ๐ ๐ ,๐ 0
contains log ๐ points.)
Observe that, for each vertical strip ๐๐ ๐
, all instances planted into ๐๐
๐
have the same vertical
shift - (๐ โ 1); the horizontal shift ๐ of each instance increases from 0 to ๐ โ 1 as we traverse
0
๐๐๐
from bottom to top. In particular, the instance planted into ๐1๐ is precisely the instance ๐ห
from Section 4.2 (if we ignore inactive rows). For each ๐ > 1, the instance planted into ๐๐
๐
is very
similar to the instance ๐ห from Section 4.2, except that each of its corresponding sub-instances is
shifted vertically by exactly (๐ โ 1) rows.
Similarly, for each horizontal strip ๐ ๐ป
๐
, all instances planted into ๐ ๐ป
๐
have the same horizontal
shift - (๐ โ 1); the vertical shift ๐ 0 of each instance increases from 0 to ๐ โ 1 as we traverse ๐ ๐ป
๐
from left to right.
Since, for every instance ๐ ๐ ,๐ , OPT(๐ ๐ ,๐ ) = ฮฉ(log ๐ log log ๐), we obtain the following bound.
0 0
ห = ฮฉ(๐ 2 log ๐ log log ๐) = ฮฉ(๐ โ log log ๐ โ ).
Observation 5.4. OPT(๐)
Since instance ๐ห is symmetric, and every point lies on one of the ๐ 2 rows of โฬ and on one of
ห we obtain the following.
the ๐ 2 rows of ๐,
ห Similarly, every column of
Observation 5.5. Every row in โฬ contains exactly log ๐ points of ๐.
๐ห contains exactly log ๐ points of ๐.
ห
5.2.4 Final instance
Lastly, in order to turn ๐ห into a permutation ๐ โ , we perform a similar transformation to that in
Section 4.2: for every column ๐ถ โ ๐, we replace ๐ถ with a collection โฌ(๐ถ) of log ๐ consecutive
columns, and we place all points that lie on ๐ถ on the columns of โฌ(๐ถ), so that they form an
increasing sequence, while preserving their ๐ฆ-coordinates. We replace every row ๐
โ โ by a
collection โฌ(๐
) of log ๐ rows similarly. The resulting final instance ๐ โ is now guaranteed to be
a permutation, and it contains ๐ โ = ๐ 2 log ๐ points. Using the same reasoning as in Section 4.2,
ห โฅ ฮฉ(๐ โ log log ๐ โ ). In the remainder of this section,
it is easy to verify that OPT(๐ โ ) โฅ OPT(๐)
we will show that cGB(๐ โ ) = ๐(๐ โ log log log ๐ โ ).
Abusing the notation, for all 1 โค ๐ โค ๐ 2 , we denote by ๐๐ ๐
the vertical strip obtained by
taking the union of all blocks โฌ(๐ถ) of columns, where ๐ถ belonged to the original strip ๐๐ ๐
. We
๐ป
define the horizontal strips ๐ ๐ similarly. Note that, from Lemma 5.2, it is enough to prove
that WB(๐ โ ) = ๐(๐ โ log log log ๐ โ ) and that WB0(๐ โ ) = ๐(๐ โ log log log ๐ โ ). We do so in the
following two subsections.
5.3 Handling vertical cuts
The goal of this section is to prove the following theorem:
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 42
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
Theorem 5.6. WB(๐ โ ) โค ๐(๐ โ log log log ๐ โ ).
For all 1 โค ๐ โค ๐, we denote by โฌ๐ the set of active columns that lie in the vertical strip ๐๐ ๐
,
so that โฌ1 , . . . , โฌ๐ partition the set of active columns of ๐ . Let โ be a collection of lines at
โ 0
half-integral coordinates that partitions the bounding box ๐ต into ๐ strips where each strip
contains exactly the block โฌ๐ of columns. We consider the split of ๐ โ by the lines โ 0: This is a
collection of ๐ strip instances (that we will denote by ๐1โ , . . . , ๐๐
โ
) and a compressed instance,
ห
that we denote by ๐. In order to prove Theorem 5.6, we bound WB(๐๐โ ) for every strip instance
๐๐โ , and WB(๐) ห for the compressed instance ๐, ห and then combine them using Theorem 3.6 in
order to obtain the final bound on WB(๐ ). โ
5.3.1 Bounding Wilber bound for strip instances
In this subsection, we prove the following lemma.
Lemma 5.7. For all 1 โค ๐ โค ๐, WB(๐๐โ ) โค ๐(๐ log ๐ log log log ๐).
From now on we fix an index ๐, and consider the instance ๐๐โ . Recall that in order to construct
instance ๐๐โ , we started with the instances ๐ 0,๐ , ๐ 1,๐ , . . . , ๐ ๐โ1,๐ , each of which has the same
vertical shift (shift ๐), and horizontal shifts ranging from 0 to ๐ โ 1. Let ๐ห ๐ be the instance
obtained by stacking these instances one on top of the other, similarly to the construction of
instance ๐ห in Section 4.2. As before, instance ๐ห ๐ is a semi-permutation, so every row contains at
most one point. Every column of ๐ห ๐ contains exactly log ๐ points of ๐ห ๐ . Let ๐ denote the set
of all active columns of instance ๐ห ๐ . For every column ๐ถ โ ๐, we replace ๐ถ with a block โฌ(๐ถ)
of log ๐ columns, and place all points of ๐ห ๐ โฉ ๐ถ on the columns of โฌ(๐ถ), so that they form an
increasing sequence, while preserving their ๐ฆ-coordinates. The resulting instance is equivalent
to ๐๐โ (to obtain instance ๐๐โ we also need to replace every active row ๐
with a block โฌ(๐
) of
log ๐ rows; but since every row contains at most one point of ๐ห ๐ , this amounts to inserting
empty rows into the instance).
The analysis of WB(๐๐โ ) is very similar to the analysis of WB(๐ โ ) for instance ๐ โ constructed in
Section 4.2. Notice that, as before, it is sufficient to show that WB(๐ห ๐ ) โค ๐(๐ log ๐ log log log ๐).
Indeed, consider the partition {โฌ(๐ถ)} ๐ถโ๐ of the columns of ๐๐โ . Then ๐ห ๐ can be viewed as the
compressed instance for ๐๐โ with the respect to this partition. Each resulting strip instance
(defined by the block โฌ(๐ถ) of columns) is an increasing sequence of log ๐ points, so the Wilber
Bound value for such an instance is ๐(log ๐). Altogether, the total Wilber Bound of all such
strip instances is ๐(๐ log ๐). Therefore, from Theorem 3.6, in order to prove Lemma 5.7, it is
now sufficient to show that WB(๐ห ๐ ) โค ๐(๐ log ๐ log log log ๐).
Let โ be the set of all vertical lines with half-integral coordinates for the instance ๐ห ๐ , and let ๐ be
any permutation of these lines. Our goal is to prove that WB๐ (๐ห ๐ ) โค ๐(๐ log ๐ log log log ๐).
Let ๐ = ๐(๐) be the partitioning tree associated with ๐. Consider some vertex ๐ฃ โ ๐(๐) and the
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 43
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
line ๐ฟ that ๐ฃ owns. As before, we classify crossings that are charged to ๐ฟ into several types. A
crossing (๐, ๐ 0) is a type-1 crossing, if ๐ and ๐ 0 both lie in the same instance ๐ ๐,๐ . We say that
instance ๐ ๐,๐ is bad for ๐ฟ, if it contributes at least one type-1 crossing to the cost of ๐ฟ. If ๐ โ ๐ ๐,๐
and ๐ 0 โ ๐ ๐ ,๐ for ๐ โ ๐ 0, then we say that (๐, ๐ 0) is a type-2 crossing. If either instance ๐ ๐,๐ or
0
๐ ๐ ,๐ is a bad instance for ๐ฟ, then the crossing is of type (2a); otherwise it is of type (2b).
0
We now bound the total number of crossings of each of these types separately.
โข Type-1 Crossings. We bound the total number of all type-1 crossings exactly like in
Section 4.3. We note that the proof does not use the vertical locations of the points in the
sub-instances ๐ ๐,๐ , and only relies on two properties of instance ๐:
ห (i) the points in the
first instance ๐0 (corresponding to instance ๐ 0,๐ ) are exponentially spaced horizontally,
so the ๐ฅ-coordinates of the points are integral powers of 2, and they are all distinct; and
(ii) each subsequent instance ๐๐ (corresponding to instance ๐ ๐ ,๐ ) is a copy of ๐0 that is
shifted horizontally by ๐ units. Therefore, the same analysis applies, and the total number
of type-1 crossings in ๐ห ๐ can be bounded by ๐(๐ log ๐ log log log ๐) as before.
โข Type-(2a) Crossings. As before, we charge each type-(2a) crossing to one of the correspond-
ing bad instances, to conclude that the total number of type-(2a) crossings is bounded by
the total number of type-1 crossings, which is in turn bounded by ๐(๐ log ๐ log log log ๐).
โข Type-(2b) Crossings. Recall that in order to bound the number of type-(2b) crossings,
we have collapsed, for every instance ๐๐ , all rows of ๐๐ into a single row. If we similarly
collapse, for every instance ๐ ๐ ,๐ , all rows of this instance into a single row, we will obtain
an identical set of points. This is because the only difference between instances ๐๐ and
๐ ๐ ,๐ is vertical position of their points. Therefore, the total number of type-(2b) crossings
in ๐ห ๐ is bounded by ๐(๐ log ๐) as before.
This finishes the proof of Lemma 5.7. We conclude that
๐
ร
WB(๐๐โ ) โค ๐(๐ 2 log ๐ log log log ๐) = ๐(๐ โ log log log ๐ โ ) . (5.1)
๐=1
5.3.2 Bounding Wilber bound for the compressed instance
In this subsection, we prove the following lemma.
ห โค ๐(๐ โ ).
Lemma 5.8. WB(๐)
We denote the active columns of ๐ห by ๐ถ1 , . . . , ๐ถ ๐ . Recall that each column ๐ถ ๐ contains exactly
๐ log ๐ input points. Let โ be the set of all rows with integral coordinates, so |โ| = ๐ 2 log ๐.
Let โฌ1 , โฌ2 , . . . , โฌ๐ 2 be a partition of the rows in โ into blocks containing log ๐ consecutive rows
each, where the blocks are indexed in their natural bottom-to-top order. Recall that each such
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 44
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
ห and the points of ๐ห that lie on the rows of โฌ๐
block โฌ๐ represents some active row of instance ๐,
form an increasing sequence. We also partition the rows of โ into super-blocks, โฌฬ1 , . . . , โฌฬ๐ ,
where each superblock is the union of exactly ๐ consecutive blocks. For each subinstance ๐ ๐ ,๐ ,
0
the points of the subinstance lie on rows that belong to a single super-block.
ห so |โ| โค ๐. We fix any
Let โ be the set of all columns with half-integral coordinates for ๐,
ห โค ๐(๐ ). Let ๐ be the partitioning tree associated
permutation ๐ of โ, and prove that WB๐ (๐) โ
with the permutation ๐.
Consider any vertex ๐ฃ โ ๐(๐), its corresponding vertical strip ๐ = ๐(๐ฃ), and the vertical line
๐ฟ = ๐ฟ(๐ฃ) that ๐ฃ owns. Let (๐, ๐ 0) be a crossing of ๐ฟ, so ๐ and ๐ 0 both lie in ๐ on opposite sides of
๐ฟ, and no point of ๐ห โฉ ๐ lies between the row of ๐ and the row of ๐ 0. Assume that the row of ๐
is below the row of ๐ 0. We say that the crossing is left-to-right if ๐ is to the left of ๐ฟ, and we say
that it is right-to-left otherwise. In order to bound the number of crossings, we use the following
two claims.
Claim 5.9. Assume that (๐, ๐ 0) is a left-to-right crossing, and assume that ๐ lies on a row of โฌ๐ and ๐ 0
lies on a row of โฌ ๐ , with ๐ โค ๐. Then either ๐ โค ๐ + 1 (so the two blocks are either identical or consecutive),
or block โฌ๐ is the last block in its super-block.
Proof. Assume that ๐ lies on column ๐ถ ๐ 0 and on a row of super-block โฌฬ๐ , so this point originally
belonged to instance ๐ ๐ ,๐ . Recall that instance ๐ ๐ ,๐ +1 (that lies immediately to the right of ๐ ๐ ,๐ )
0 0 0
is obtained by circularly shifting all points in instance ๐ ๐ ,๐ by one unit up. In particular, a copy
0
๐ ๐ of ๐ in ๐ ๐ ,๐ +1 should lie one row above the copy of ๐ in ๐ ๐ ,๐ , unless ๐ lies on the last row of
0 0
๐ ๐ ,๐ . In the latter case, block โฌ๐ must be the last block of its superblock โฌฬ๐ . In the former case,
0
since point ๐ ๐ does not lie between the row of ๐ and the row of ๐ 0, and it lies on column ๐ถ ๐ +1 ,
the block of rows in which point ๐ 0 lies must be either โฌ๐ or โฌ๐+1 , that is, ๐ โค ๐ + 1.
Claim 5.10. Assume that (๐, ๐ 0) is a right-to-left crossing, and assume that ๐ lies on a row of โฌ๐ and ๐ 0
lies on a row of โฌ ๐ , with ๐ โค ๐. Then either (i) ๐ โค ๐ + 1 (so the two blocks are identical or consecutive); or
(ii) block โฌ๐ is the last block in its super-block; or (iii) block โฌ ๐ is the first block it its super-block; or (iv) ๐
lies on the last active column in strip ๐, and ๐ 0 lies on the first active column in strip ๐.
Proof. Assume that ๐ lies on column ๐ถ ๐ 0 and on a row of superblock โฌฬ๐ , so this point originally
belonged to instance ๐ ๐ ,๐ . Assume for that ๐ถ ๐ 0 is not the last active column of ๐, so ๐ถ ๐ 0+1 also
0
lies in ๐.
Recall that instance ๐ ๐ ,๐ +1 is obtained by circularly shifting all points in instance ๐ ๐ ,๐ by one
0 0
unit up. In particular, a copy ๐ ๐ of ๐ in ๐ ๐ ,๐ +1 should lie one row above the copy of ๐ in ๐ ๐ ,๐ ,
0 0
unless ๐ lies on the last row of ๐ ๐ ,๐ . In the latter case, block โฌ๐ must be the last block of its
0
superblock. In the former case, since point ๐ ๐ does not lie between the row of ๐ and the row of
๐ 0, the block of rows in which point ๐ 0 lies is either โฌ๐ or โฌ๐+1 , that is, ๐ โค ๐ + 1.
Using a symmetric argument, if ๐ 0 does not lie on the first active column of ๐, then either
๐ โค ๐ + 1, or โฌ ๐ is the first block in its super-block.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 45
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
We can now categorize all crossings charged to the line ๐ฟ into types as follows. Let (๐, ๐ 0) be a
crossing, and assume that ๐ lies on a row of โฌ๐ , ๐ 0 lies on a row of โฌ ๐ , and ๐ โค ๐. We say that
(๐, ๐ 0) is a crossing of type 1, if ๐ โค ๐ + 1. We say that it is a crossing of type 2 if either โฌ๐ or โฌ ๐
are the first or the last blocks in their superblock. We say that it is of type 3 if ๐ lies on the last
active column of ๐ and ๐ 0 lies on the first active column of ๐.
We now bound the total number of all such crossings separately.
โข Type-1 crossings Consider any pair โฌ๐ , โฌ๐+1 of consecutive blocks, and let ๐ห ๐0 be the set
of all points lying on the rows of these blocks. Recall that all points lying on the rows
of โฌ๐ form an increasing sequence of length log ๐, and the same is true for all points
lying on the rows of โฌ๐+1 . It is then easy to see that OPT(๐ห ๐0) โค ๐(log ๐), and so the total
contribution of crossings between the points of ๐ห ๐0 to WB๐ (๐) ห is bounded by ๐(log ๐).
Since the total number of blocks โฌ๐ is bounded by ๐ , the total number of type-1 crossings
2
is at most ๐(๐ 2 log ๐).
โข Type-2 crossings In order to bound the number of type-2 crossings, observe that |โ| โค ๐.
If ๐ฟ โ โ is a vertical line, and ๐ is a strip that ๐ฟ splits, then there are ๐ superblocks of rows
that can contribute type-2 crossings to cost(๐ฟ), and each such superblock may contribute
at most one crossing. Therefore, the total number of type-2 crossings charged to ๐ฟ is at
most ๐, and the total number of all type-2 crossings is ๐(๐ 2 ).
โข Type-3 crossings In order to bound the number of type-3 crossings, observe that every
column contains ๐ log ๐ points. Therefore, if ๐ฟ โ โ is a vertical line, then the number
of type-3 crossings charged to it is at most 2๐ log ๐. As |โ| โค ๐, we get that the total
number of type-3 crossings is ๐(๐ 2 log ๐).
To conclude, we have shown that WB๐ (๐) ห = ๐(๐ 2 log ๐) = ๐(๐ โ ), proving Lemma 5.8. By
combining Lemmas 5.7 and 5.8, together with Theorem 3.6, we conclude that WB(๐ โ ) =
๐(๐ โ log log log ๐ โ ), proving Theorem 5.6.
5.4 Handling horizontal cuts
We show the following analogue of Theorem 5.6.
Theorem 5.11. WB0(๐ โ ) โค ๐(๐ โ log log log ๐ โ ).
The proof of the theorem is virtually identical to the proof of Theorem 5.6. In fact, consider
the instance ๐ โโ , that is obtained from ๐ โ , by rotating it by 90 degrees clockwise. Consider the
sequence BRS0(โ , โ, ๐) that is obtained by rotating the point set BRS(โ , โ, ๐) by 90 degrees.
Consider now the following process. Our starting point is the rotated Bit Reversal Sequence. We
then follow exactly the same steps as in the construction of the instance ๐ โ . Then the resulting
instance is precisely (a mirror reflection of) instance ๐ โโ . Notice that the only place where our
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 46
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
proof uses the fact that we start with the Bit Reversal Sequence is in order to show that OPT(๐ โ )
is sufficiently large. In fact we could replace the Bit Reversal Sequence with any other point
set that is a permutation, and whose optimal solution cost is as large, and in particular the Bit
Reversal Sequence that is rotated by 90 degrees would work just as well. The analysis of the
Wilber Bound works exactly as before, and Theorem 5.11 follows.
6 Algorithmic results
6.1 Overview
We provide the high level intuition for the proof of Theorem 1.2. Both the polynomial time and
the subexponential time algorithms follow the same framework. We start with a high-level
overview of this framework. For simplicity, assume that the number of active columns in the
input instance ๐ is an integral power of 2. The key idea is to decompose the input instance into
smaller sub-instances, using the split instances defined in Section 3.1. We solve the resulting
instances recursively and then combine the resulting solutions.
Suppose we are given an input point set ๐ that is a semi-permutation, with |๐ | = ๐, such that
the number of active columns is ๐. We consider a balanced partitioning tree ๐, where for every
vertex ๐ฃ โ ๐(๐), the line ๐ฟ(๐ฃ) that ๐ฃ owns splits the strip ๐(๐ฃ) in the middle, with respect to the
active columns that are contained in ๐(๐ฃ). Therefore, the height of the partitioning tree is log ๐.
Consider now the set ๐ of verticesโ of ๐ that lie in the middle layer of ๐. Let โ 0 be their strip
boundaries, so we have |โ | = ฮ( ๐). Consider the split of ๐ by โ , obtaining a new collection
0 0
โ
e , {๐๐ }) ๐ where ๐ = ฮ( ๐). Note that each resulting strip instance ๐๐ contains
of instances (๐
โ ๐=1
ฮ( ๐) active columns, and so does the compressed instance ๐. e
We recursively solve each such instance and then combine the resulting solutions. The key to
the algorithm and its analysis is to show that there is a collection ๐ of ๐(|๐ |) points, such that,
if we are given
any solution
๐
b to instance ๐,
e and, for all 1 โค ๐ โค ๐, any solution ๐๐ to instance ๐๐ ,
ร๐
then ๐ โช ๐
bโช
๐=1 ๐๐ is a feasible solution to instance ๐. We also show that the total number of
input points that appear in all instances that participate in the same recursive level is bounded
by ๐(OPT(๐)). This ensures that in every recursive level we add at most ๐(OPT(๐)) points to
the solution, and the total solution cost is at most ๐(OPT(๐)) times the number of the recursive
levels, which is bounded by ๐(log log ๐).
In order to obtain the subexponential time algorithm, we restrict the recursion to ๐ท levels, and
then solve each resulting instance ๐ 0 directly in time ๐(๐ 0)๐(๐ 0)๐(๐(๐ )) . This approach gives
0
ฮฉ(๐ท)
an ๐(๐ท)-approximation algorithm with running time at most poly(๐) ยท exp ๐ 1/2 log ๐ as
desired.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 47
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
(a) Canonical Solution (b) Special Solution
Figure 7: Canonical and ๐-special solutions of ๐. The input points are shown as circles; the
points that belong to the solution ๐ are shown as squares.
6.2 Special solutions and reduced sets
Our algorithm will produce feasible solutions of a special form, that we call special solutions.
Recall that, given a semi-permutation point set ๐, the auxiliary columns for ๐ are a set โ of
vertical lines with half-integral coordinates. We say that a solution ๐ for ๐ is special iff every
point of ๐ lies on an row that is active for ๐, and on a column of โ. In particular, special
solutions are by definition non-canonical (see Figure 7 for an illustration).
If ๐0 is any ordering of the auxiliary columns in โ 0 โ โ, and ๐ 0 = ๐(๐0) is the corresponding
partitioning tree, then any point set ๐ that is a special solution for ๐ is also called a ๐ 0-special
solution: The solutions use only auxiliary columns in โ 0 (equivalently, strip boundaries of ๐(๐ฃ)
for ๐ฃ โ ๐(๐ 0)).
Consider a semi-permutation ๐, that we think of as a potential input to the Min-Sat problem.
We denote ๐ = {๐ 1 , . . . , ๐ ๐ }, where the points are indexed in their natural bottom-to-top order,
so (๐ 1 ).๐ฆ < (๐ 2 ).๐ฆ < . . . < (๐ ๐ ).๐ฆ. A point ๐ ๐ is said to be redundant, if and only if the points
immediately above and below are on its column, that is, for some ๐, (๐ ๐ ).๐ฅ = (๐ ๐+1 ).๐ฅ = (๐ ๐โ1 ).๐ฅ.
We say that a semi-permutation ๐ is in the reduced form if there are no redundant points in ๐.
The following lemma relates the optimal solutions of any instance and its reduced form.
Lemma 6.1. Let ๐ be a semi-permutation, and let ๐ 0 โ ๐ be any point set, that is obtained from ๐ by
repeatedly removing redundant points. Then OPT(๐ 0) โค OPT(๐). Moreover, if ๐ is a feasible solution
for ๐ 0 such that every point of ๐ lies on a row that is active for ๐ 0, then ๐ is also a feasible solution for ๐.
Proof. For the first claim, it is sufficient to show that, if ๐ 00 is a set of points obtained from ๐ by
deleting a single redundant point ๐ ๐ , then OPT(๐ 00) โค OPT(๐). Let ๐
denote the row on which
point ๐ ๐ lies, and let ๐
0 be the row containing ๐ ๐โ1 . Let ๐ be the optimal solution to instance
๐. We assume w.l.o.g. that ๐ is a canonical solution. Consider the set ๐ = ๐ โช ๐ of point, and
let ๐0 be obtained from ๐ by collapsing the rows ๐
, ๐
0 into the row ๐
0 (since ๐ is a canonical
solution for ๐, no points of ๐ โช ๐ lie strictly between the rows ๐
, ๐
0). From Observation 2.4, ๐0
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 48
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
remains a satisfied point set. Setting ๐ 0 = ๐0 \ ๐ 00, it is easy to verify that ๐ 0 is a feasible solution
to instance ๐ 00, and moreover, |๐ 0 | โค |๐|. Therefore, OPT(๐ 00) โค |๐ 0 | โค |๐| โค OPT(๐).
As for the second claim, it is sufficient to show that, if ๐ 00 is a set of points obtained from ๐ by
deleting a single redundant point ๐ ๐ , and ๐ is any canonical solution for ๐ 00, then ๐ is also a
feasible solution for ๐. We can then apply this argument iteratively, until we obtain a set of
points that is in a reduced form.
Consider any feasible canonical solution ๐ to instance ๐ 00. We claim that ๐ โช ๐ is a feasible set
of points. Indeed, consider any two points ๐, ๐ โ ๐ โช ๐ that are not aligned. If both points are
distinct from the point ๐ ๐ , then they must be satisfied in ๐ โช ๐, since both these points lie in
๐ 00 โช ๐. Therefore, we can assume that ๐ = ๐ ๐ . Notice that ๐ โ ๐ ๐โ1 and ๐ โ ๐ ๐+1 , since otherwise
๐ and ๐ must be aligned. Moreover, ๐ cannot lie strictly between the row of ๐ ๐โ1 and the row of
๐ ๐+1 , as we have assumed that every point of ๐ lies on a row that is active for ๐ 0 ๐ 00. But then
it is easy to verify that either point ๐ ๐โ1 lies in ๐,๐ (if ๐ is below ๐), or point ๐ ๐+1 lies in ๐,๐
(otherwise). In either case, the pair (๐, ๐) is satisfied in ๐ โช ๐.
From Lemma 6.1, whenever we need to solve the Min-Sat problem on an instance ๐, it is sufficient
to solve it on a sub-instance, obtained by iteratively removing redundant points from ๐. We
obtain the following immediate corollary of Lemma 6.1.
Corollary 6.2. Let ๐ be a semi-permutation, and let ๐ 0 โ ๐ be any point set, that is obtained from ๐
by repeatedly removing redundant points. Let ๐ be any special feasible solution for ๐ 0. Then ๐ is also a
special feasible solution for ๐.
Lastly, we need the following lemma, which is a simple application of the Wilber bound.
Lemma 6.3. Let ๐ be a point set that is a semi-permutation in reduced form. Then OPT(๐) โฅ |๐ |/4 โ 1.
Proof. Since ๐ is a semi-permutation, every point of ๐ lies on a distinct row; we denote |๐ | = ๐.
Let ๐ = {๐ 1 , . . . , ๐ ๐ }, where the points are indexed in the increasing order of their ๐ฆ-coordinates.
Let ฮ = {(๐ ๐ , ๐ ๐+1 ) | 1 โค ๐ < ๐} be the collection of all consecutive pairs of points in ๐. We say
that the pair (๐ ๐ , ๐ ๐+1 ) is bad iff both ๐ ๐ and ๐ ๐+1 lie on the same column. From the definition of
the reduced form, if (๐ ๐ , ๐ ๐+1 ) is a bad pair, then both (๐ ๐โ1 , ๐ ๐ ) and (๐ ๐+1 , ๐ ๐+2 ) are good pairs.
Let ฮ 0 โ ฮ be the subset containing all good pairs. Then |ฮ 0 | โฅ (|ฮ | โ 1)/2 โฅ ๐/2 โ 1. Next, we
select a subset ฮ 00 โ ฮ 0 of pairs, such that |ฮ 00 | โฅ |ฮ 0 |/2 โฅ ๐/4 โ 1, and every point in ๐ belongs
to at most one pair in ฮ 00. Since every point in ๐ belongs to at most two pairs in ฮ 0, it is easy to
see that such a set exists. Let ๐ be an optimal solution to instance ๐.
Consider now any pair (๐ ๐ , ๐ ๐+1 ) of points in ฮ 00. Then there must be a point ๐ฆ ๐ โ ๐ that lies in
the rectangle ๐ ๐ ,๐ ๐+1 . Moreover, since all points of ๐ lie on distinct rows, and each such point
belongs to at most one pair in ฮ 00, for ๐ โ ๐, ๐ฆ ๐ โ ๐ฆ ๐ . Therefore, |๐| โฅ |ฮ 00 | โฅ ๐/4 โ 1.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 49
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
6.3 Our algorithm
Suppose we are given an input set ๐ of points that is a semi-permutation. Let ๐ be any
partitioning tree for ๐. We say that ๐ is a balanced partitioning tree for ๐ iff for every non-leaf
vertex ๐ฃ โ ๐(๐) and its children ๐ฃ 1 , ๐ฃ2 , the number of active columns inside ๐(๐ฃ 1 ) and ๐(๐ฃ 2 ) are
roughly the same, that is, ๐(๐ โฉ ๐(๐ฃ ๐ )) โค d๐(๐ โฉ ๐(๐ฃ))/2e for each ๐ = 1, 2.
Given a partitioning tree ๐, we denote by ฮ๐ the set of all vertices of ๐ that lie in the ๐th layer
of ๐ โ that is, the vertices whose distance from the root of ๐ is ๐ (so the root belongs to ฮ0 ).
The height of the tree ๐, denoted by height(๐), is the largest index ๐ such that ฮ๐ โ โ
. If the
height of the tree ๐ is โ, then we call the set ฮ dโ/2e of vertices the middle layer of ๐. Notice that,
if ๐ is a balanced partitioning tree for input ๐, then its height is at most 2 log ๐(๐). The strips
{๐(๐ฃ)} ๐ฃโฮ dโ/2e are called the middle-layer strips.
Our algorithm takes as input a set ๐ of points that is a semi-permutation, a balanced partition
tree ๐ for ๐, and an integral parameter ๐ > 0.
Intuitively, the algorithm uses the splitting operation to partition the instance ๐ into subinstances
that are then solved recursively, until it obtains a collection of instances whose corresponding
partitioning trees have height at most ๐. We then employ dynamic programming. The algorithm
returns a special feasible solution for the instance. Recall that the height of the tree ๐ is bounded
by 2 log ๐(๐) โค 2 log ๐. The following theorem (whose proof appears in Section 6.6) is used as
a recursion basis.
Theorem 6.4. There is an algorithm called LeafBST that, given a semi-permutation instance ๐ of
Min-Sat in reduced form, and a partitioning tree ๐ for it, produces a feasible ๐-special solution for ๐ of
cost at most 2|๐ | + 2OPT(๐), in time |๐ | ๐(1) ยท ๐(๐)๐(๐(๐)) .
We now provide a schematic description of our algorithm.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 50
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
RecursiveBST(๐ , ๐, ๐)
1. Keep removing redundant points from ๐ until ๐ is in reduced form.
2. If ๐ has height at most ๐,
3. return LeafBST(๐ , ๐)
4. Let โ 0 โ โ be the strip boundaries of the middle-layer strips {๐1 , . . . , ๐ ๐ }
of ๐.
5. Compute the split (๐
e , {๐ ๐ } ๐โ[๐] ) of ๐ by โ 0.
6. Compute the corresponding split subtrees (๐,
e {๐๐ } ๐โ[๐] ) of ๐ by โ 0.
7. For ๐ โ [๐], call to RecursiveBST with input (๐ ๐ , ๐๐ , ๐), and let ๐๐ be the
solution returned by it.
8. Call RecursiveBST with input (๐ e ๐), and let ๐ห be the solution returned
e , ๐,
by it.
9. Let ๐ be a point set containing, for each ๐ โ [๐], for each point ๐ โ ๐ ๐ ,
two copies ๐ 0 and ๐ 00 of ๐ with ๐ 0 .๐ฆ = ๐ 00 .๐ฆ = ๐.๐ฆ, where ๐ 0 lies on the left
boundary of ๐ ๐ , and ๐ 00 lies on the right boundary of ๐ ๐ .
10. return ๐ โ = ๐ โช ๐ห โช ( ๐โ[๐] ๐๐ )
ร
The cost and feasibility analyses appear in the next two subsections.
6.4 Cost analysis
In order to analyze the solution cost, consider the final solution ๐ โ to the input instance ๐. We
distinguish between two types of points in ๐ โ : a point ๐ โ ๐ โ is said to be of type 2 if it was
added to the solution by Algorithm LeafBST, and otherwise we say that it is of type 1. We start
by bounding the number of points of type 1 in ๐ โ .
Claim 6.5. The number of points of type 1 in the solution ๐ โ to the original instance ๐ is at most
๐(log(height(๐)/๐)) ยท OPT(๐).
Proof. Observe that the number of recursive levels is bounded by ๐ = ๐(log(height(๐)/๐)). This
is since, in every recursive level, the heights of all trees decrease by a constant factor, and we
terminate the algorithm once the tree heights are bounded by ๐. For each 1 โค ๐ โค ๐, let ๐ณ๐ be the
collection of all instances in the ๐th recursive level, where the instances are in the reduced form.
Notice that the only points that are added to the solution by Algorithm RecursiveBST directly
are the points in the sets ๐. The number of such points added at recursive level ๐ is bounded by
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 51
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
๐ 0 โ๐ณ๐ 2|๐ |. It is now sufficient to show that for all 1 โค ๐ โค ๐, ๐ 0 โ๐ณ๐ |๐ | โค ๐(OPT(๐)). We do
ร 0 ร 0
so using the following observation.
Observation 6.6. For all 1 โค ๐ โค ๐, 0
ร
๐ 0 โ๐ณ๐ OPT(๐ ) โค OPT(๐).
Assume first that the observation is correct. From Lemma 6.3, |๐ 0 | โค ๐(OPT(๐ 0)). Therefore,
the number of type-1 points added to the solution at recursive level ๐ is bounded by ๐(OPT(๐)).
We now turn to prove Observation 6.6.
Proof of Observation 6.6. The proof is by induction on the recursive level ๐. It is easy to see that
the claim holds for ๐ = 1, since, from Lemma 6.1, removing redundant points from ๐ to turn it
into reduced form cannot increase OPT(๐).
Assume now that the claim holds for level ๐ โ 1, and consider some level-๐ instance ๐ 0 โ ๐ณ๐ . Let
(๐ , ๐ ๐ ๐โ[๐] ) be the split of ๐ 0 that we computed. Then, from Theorem 3.3, ๐โ[๐] OPT(๐ ๐ ) +
ร
e
OPT(๐)
e โค OPT(๐ 0). Since, from Lemma 6.1, removing redundant points from an instance does
not increase its optimal solution cost, the observation follows.
In order to obtain an efficient ๐(log log ๐)-approximation algorithm, we set ๐ to be a constant (it
can even be set to 1), and we use algorithm LeafBST whenever the algorithm calls to subroutine
LeafBST. Observe that the depth of the recursion is now bounded by ๐(log log ๐), and so the
total number of type-1 points in the solution is bounded by ๐(log log ๐) ยท OPT(๐). Let โ denote
the set of all instances to which Algorithm LeafBST is applied. Using the same arguments as
in Claim 6.5, ๐ 0 โโ |๐ 0 | = ๐(OPT(๐)). The number of type-2 points that Algorithm LeafBST
ร
adds to the solution for each instance ๐ 0 โ โ is bounded by ๐(OPT(๐ 0) + |๐ 0 |) = ๐(|๐ 0 |).
Therefore, the total number of type-2 points in the solution is bounded by ๐(OPT(๐)). Overall,
we obtain a solution of cost at most ๐(log log ๐) ยท OPT(๐), and the running time of the algorithm
is polynomial in |๐ |.
Finally, in order to obtain the subexponential time algorithm, we set the parameter ๐ to be such
that the recursion depth is bounded by ๐ท. Since the number of active columns in instance
๐ is ๐(๐), and the height of the partitioning tree ๐ is bounded by 2 log ๐(๐), whilethe depth
log ๐(๐) log ๐(๐)
of the recursion is at most 2 log(height(๐)/๐), it is easy to verify that ๐ = ๐ 2๐ท/2
= 2ฮฉ(๐ท)
.
As before, let โ be the set of all instances to which Algorithm LeafBST is applied. Using
the same arguments as in Claim 6.5, ๐ 0 โโ (|๐ 0 | + OPT(๐ 0)) = ๐(OPT(๐)). For each such
ร
instance ๐ 0, Algorithm LeafBST produces a solution of cost ๐(|๐ 0 | + OPT(๐ 0)). Therefore,
the total number of type-2 points in the final solution is bounded by ๐(OPT(๐)). The total
number of type-1 points in the solution is therefore bounded by ๐(๐ท) ยท OPT(๐) as before.
Therefore, the algorithm produces a factor-๐(๐ท)-approximate solution. Finally, in order to
analyze the running time of the algorithm, we first bound the running time of all calls to
procedure LeafBST. The number of such calls is bounded by |๐ |. Consider now some instance
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 52
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
๐ 0 โ โ, and its corresponding partitioning tree ๐ 0. Since the height of ๐ 0 is bounded by ๐,
we get that ๐(๐ 0) โค 2๐ โค 2log ๐(๐)/2
ฮฉ(๐ท) ฮฉ(๐ท)
โค (๐(๐))1/2 . Therefore, the running time of LeafBST
on instance ๐ 0 0 ๐(1) ยท (๐(๐ 0 ))๐(๐(๐ 0 )) โค |๐ 0 | ๐(1) ยท exp ๐(๐(๐ 0 ) log ๐(๐ 0 ) โค
is bounded by |๐ |
|๐ 0 | ๐(1) ยท exp ๐(๐)1/2
ฮฉ(๐ท)
ยท log ๐(๐) .
The running time of the remainder of the algorithm, excluding the calls to LeafBST, is bounded
by poly(|๐ |). We conclude that the total running time of the algorithm is bounded by
๐(1) 1/2ฮฉ(๐ท) 1/2ฮฉ(๐ท)
|๐ | ยท exp ๐(๐) ยท log ๐(๐) โค poly(๐) ยท exp ๐ ยท log ๐
6.5 Feasibility
We start by showing that the solution that the algorithm returns is ๐-special.
Observation 6.7. Assuming that LeafBST(๐ , ๐) returns a ๐-special solution, the solution ๐ โ
returned by Algorithm RecursiveBST(๐ , ๐, ๐) is a ๐-special solution.
Proof. The proof is by induction on the recursion depth. The base of the induction is the calls to
Procedure LeafBST(๐ , ๐), which return ๐-special solutions by our assumption. Consider now
some call to Algorithm RecursiveBST(๐ , ๐, ๐). From the induction hypothesis, the resulting
solution ๐ห for instance ๐ e is ๐-special,
e and, for every strip ๐ โ [๐], the resulting solution ๐๐ for
instance ๐ ๐ is ๐๐ -special. Since both ๐
e and every tree ๐๐ are subtrees of ๐, and since the
๐โ[๐]
points of ๐ lie on boundaries of strips in ๐ ๐ ๐โ[๐] , the final solution ๐ โ is ๐-special.
We next turn to prove that the solution ๐ โ computed by Algorithm RecursiveBST(๐ , ๐, ๐) is
feasible. In order to do so, we will use the following immediate observation.
Observation 6.8. Let ๐ โ be the solution returned by Algorithm RecursiveBST(๐ , ๐, ๐), and let
๐ โ [๐] be any strip index. Then:
โข Any point ๐ฆ โ ๐ โ that lies in the interior of ๐ ๐ must lie on an active row of instance ๐ ๐ .
โข Any point ๐ฆ โ ๐ โ that lies on the boundary of ๐ ๐ must belong to in ๐ห โช ๐. Moreover, the
points of ๐ห โช ๐ may not lie in the interior of ๐ ๐ .
โข If ๐
is an active row for instance ๐ ๐ , then set ๐ contains two points, lying on the intersection
of ๐
with the left and the right boundaries of ๐ ๐ , respectively.
We are now ready to prove that the algorithm returns feasible solutions. In the following proof,
when we say that a row ๐
is an active row of strip ๐ ๐ (or equivalently of instance ๐ ๐ ), we mean
that some (input) point of instance ๐ ๐ lies on row ๐
.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 53
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
Theorem 6.9. Assume that the recursive calls to Algorithm RecursiveBST return a feasible special
solution ๐ห for instance ๐,
e and for each ๐ โ [๐], a feasible special solution ๐๐ for the strip instance ๐ ๐ .
Then the point set ๐ = ๐ โช ๐ห โช ( ๐โ[๐] ๐๐ ) is a feasible solution for instance ๐.
โ ร
Proof. It would be convenient for us to consider the set of all points in ๐
e โช ๐ โช ๐ โ simultaneously.
In order to do so, we start with the set ๐ โช ๐ of points. For every ๐ โ [๐], we select an arbitrary
โ
active column ๐ถ ๐ in strip ๐ ๐ , and we then add a copy of every point ๐ โ ๐ ๐ to column ๐ถ ๐ . The
resulting set of points, obtained after processing all strips ๐ ๐ is identical to the set ๐
e of points
(except possibly for horizontal spacing between active columns), and we do not distinguish
between them.
Consider any pair of points ๐, ๐ that lie in ๐ โ โช ๐, which are not aligned. Our goal is to prove
that some point ๐ โ ๐, ๐ with ๐ โ ๐ โช ๐ โ lies in ๐,๐ . We assume w.l.o.g. that ๐ lies to the left of
๐. We also assume that ๐.๐ฆ < ๐.๐ฆ (that is, point ๐ is below point ๐); the other case is symmetric.
Assume first that at least one of the two points (say ๐) lies in the interior of a strip ๐ ๐ , for some
๐ โ [๐]. We then consider two cases. First, if ๐ also lies in the interior of the same strip, then
๐, ๐ โ ๐ ๐ โช ๐๐ , and, since we have assumed that ๐๐ is a feasible solution for instance ๐ ๐ , the two
points are satisfied in ๐ ๐ โช ๐๐ , and hence in ๐ โช ๐ โ . Otherwise, ๐ does not lie in the interior of
strip ๐ ๐ . Then, from Observation 6.8, if ๐
is the row on which point ๐ lies, then ๐
is an active row
for instance ๐ ๐ , and the point that lies on the intersection of the row ๐
and the right boundary
of strip ๐ ๐ was added to ๐. This point satisfies the pair (๐, ๐).
Therefore, we can now assume that both ๐ and ๐ lie on boundaries of strips ๐ ๐ | ๐ โ [๐] . Since
every pair of consecutive strips share a boundary, and since, from the above assumptions, ๐ lies
to the left of ๐, we can choose the strips ๐ ๐ and ๐ ๐ , such that ๐ lies on the left boundary of ๐ ๐ ,
and ๐ lies on the right boundary of ๐ ๐ . Notice that it is possible that ๐ ๐ = ๐ ๐ .
Notice that, if ๐ lies on a row that is active for strip ๐ ๐ , then a point that lies on the same row
and belongs to the right boundary of the strip ๐ ๐ has been added to ๐; this point satisfies the
pair (๐, ๐). Similarly, if ๐ lies on a row that is active for strip ๐ ๐ , the pair (๐, ๐) is satisfied by a
point of ๐ that lies on the same row and belongs to the left boundary of ๐ ๐ .
Therefore, it remains to consider the case where point ๐ lies on a row that is inactive for ๐ ๐ , and
point ๐ lies on a row that is inactive for ๐ ๐ . From Observation 6.8, both ๐ and ๐ belong to ๐ห โช ๐.
The following observation will be useful for us. Recall that the points of ๐
e are not included in
๐ โช๐ .โ
Observation 6.10. Assume that there is some point ๐ โ ๐, ๐, such that ๐ โ ๐,๐ , and ๐ โ ๐.
e Then
the pair (๐, ๐) is satisfied in set ๐ โช ๐ .
โ
Proof. Since ๐ โ ๐,
e and ๐ โ ๐,๐ , there must be some strip ๐ ๐ , that lies between strips ๐ ๐ and ๐ ๐
(where ๐ โค ๐ โค ๐), such that point ๐ lies on the column ๐ถ ๐ (recall that this is the unique active
column of ๐ ๐ that may contain points of ๐).
e But then the row ๐
to which point ๐ belongs is
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 54
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
an active row for strip ๐ ๐ . Therefore, two points, lying on the intersection of ๐
with the two
boundaries of strip ๐ ๐ were added to ๐, and at least one of these points must lie in ๐,๐ . Since
๐ โ ๐ โ , the observation follows.
From the above observation, it is sufficient to show that some point ๐ โ ๐ห โช ๐ โช ๐
e that is distinct
from ๐ and ๐, lies in ๐,๐ . We distinguish between three cases.
The first case happens when ๐, ๐ โ ๐. ห Since set ๐ห is a feasible solution for instance ๐,
e there is
ห
some point ๐ โ ๐,๐ that is distinct from ๐ and ๐, and lies in ๐ โช ๐. e
The second case happens when neither ๐ nor ๐ lie in ๐, ห so both ๐, ๐ โ ๐. Consider strip ๐ ๐โ1
lying immediately to the left of strip ๐ ๐ . Since ๐ lies on a row that is inactive for strip ๐ ๐ , but
๐ โ ๐, such a strip must exist, and moreover, the row ๐
to which ๐ belongs must be active for
strip ๐ ๐โ1 . Therefore, the point lying on the intersection of the column ๐ถ ๐โ1 (the unique active
column of ๐ ๐โ1 containing points of ๐) e and ๐
belongs to ๐;e we denote this point by ๐ 0.
Similarly, consider strip ๐ ๐+1 lying immediately to the right of ๐ ๐ . Since ๐ lies on a row that is
inactive for strip ๐ ๐ , but ๐ โ ๐, such a strip must exist, and moreover, the row ๐
0 to which ๐
belongs must be active for strip ๐ ๐+1 . Therefore, the point lying on the intersection of ๐ถ ๐+1 and
๐
0 belongs to ๐;
e we denote this point by ๐ 0.
Since the set ๐ e โช ๐ห of points is satisfied, some point ๐ โ ๐
e โช ๐ห that is distinct from ๐ 0 and ๐ 0,
lies in ๐0 ,๐0 . Moreover, from Observation 2.3, we can choose this point so that it lies on the
boundary of the rectangle ๐0 ,๐0 . Assume first that ๐ lies on the left boundary of this rectangle.
Then, since ๐ห is a special solution for instance ๐, e ๐โ๐ e must hold. If ๐
00 denotes the row on
which ๐ lies, then ๐
is an active row for strip ๐ ๐โ1 , and so a point that lies on the intersection of
00
row ๐
00 and the right boundary of ๐ ๐โ1 belongs to ๐. That point satisfies ๐,๐ . The case where ๐
lies on the right boundary of ๐0 ,๐0 is treated similarly.
Assume now that ๐ lies on the top or the bottom boundary of ๐0 ,๐0 , but not on one of its corners.
Then, since solution ๐ห is special for ๐,
e point ๐ must lie in the rectangle ๐,๐ . Moreover, since we
have assumed that neither ๐ nor ๐ lie in ๐, ห ๐ โ ๐, ๐. But then ๐ โ ๐e โช ๐ห lies in ๐,๐ \ {๐, ๐} and
by Observation 6.10, pair (๐, ๐) is satisfied in ๐ โช ๐ .
โ
The third case happens when exactly one of the two points (say ๐) lies in ๐, ห and the other point
ห
does not lie in ๐, so ๐ โ ๐ must hold. We define the point ๐ โ ๐ exactly as in the second
0 e
case. Since ๐, ๐ 0 โ ๐ e โช ๐,ห there must be a point ๐ โ ๐,๐0 \ {๐, ๐ 0 } that lies in ๐ e โช ๐.ห From
Observation 6.8, we can choose the point ๐, so that it lies on the left or on the bottom boundary
of ๐,๐0 (that is, its ๐ฅ- or its ๐ฆ-coordinate is aligned with the point ๐). If ๐ lies on the left boundary
of ๐,๐0 , then it also lies in ๐,๐ , and from Observation 6.10, pair (๐, ๐) is satisfied in ๐ โช ๐ โ . If it
lies on the bottom boundary of ๐,๐0 , but it is not the bottom right corner of the rectangle, then,
using the same reasoning as in Case 2, it must lie in ๐,๐ , and it is easy to see that ๐ โ ๐. Lastly,
if ๐ is the bottom right corner of ๐,๐0 , then ๐ โ ๐.e As before, there is a copy of ๐, that lies on the
left boundary of strip ๐ ๐+1 and belongs to ๐, that satisfies the pair (๐, ๐).
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 55
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
6.6 Leaf instances (proof of Theorem 6.4)
The goal of this subsection is to prove Theorem 6.4. For convenience, given an input instance
๐ of Min-Sat, we denote ๐(๐) = ๐ and ๐(๐) = ๐. Our goal is to compute an optimal canonical
solution ๐ for ๐ in time poly(๐) ยท ๐ ๐(๐) . The solution can then be turned into a special one using
the following observation.
Observation 6.11. There is an algorithm, that, given a set ๐ of points that is a semi-permutation,
and a canonical solution ๐ for ๐, computes a special solution ๐ 0 for ๐, such that |๐ 0 | โค 2|๐ | +2|๐|.
Proof. We construct ๐ 0 as follows: For each point ๐ โ ๐ โช ๐, we add two points, ๐ 0 and ๐ 00 to ๐ 0,
whose ๐ฆ-coordinate is the same as that of ๐, such that ๐ 0 and ๐ 00 lie on the lines of โ appearing
immediately to the left and immediately to the right of ๐, respectively. It is easy to verify that
|๐ 0 | = 2|๐ | + 2|๐| and that ๐ 0 is a special solution.
We now verify that ๐ โช ๐ 0 is a satisfied set of points. Consider two points ๐, ๐ in ๐ โช ๐ 0, such that
๐.๐ฅ < ๐.๐ฅ. Notice that ๐ is either an original point in ๐ or it is a copy of some point ๐ห โ ๐ โช ๐.
If ๐ โ ๐ or ๐ = ๐ห 0 for ๐ห โ ๐ โช ๐, then the point ๐ห 00 lies in the rectangle ๐,๐ . Therefore, we can
assume that ๐ = ๐ห 00 for some point ๐ห โ ๐ โช ๐. By a similar reasoning, we can assume that ๐ = ๐ห 0
for some point ๐ห โ ๐ โช ๐. Since ๐ โช ๐ is a satisfied point set, there must be a point ๐ โ ๐ โช ๐
that lies in the rectangle ๐, ห ๐ห . From Observation 2.3, we can choose ๐ such that either ๐.๐ฅ = ๐.๐ฅ ห
or ๐.๐ฆ = ๐.๐ฆ.
ห In either case, point ๐ also lies in ๐ห 00 , ๐ห 0 = ๐,๐ , so (๐, ๐) is satisfied by ๐ โช ๐ 0.
00
Therefore, ๐ โช ๐ 0 is a satisfied set of points.
This observation allows us to turn the optimal canonical solution into a special solution of cost at
most 2|๐ | + 2|๐| โค 2|๐ | + 2OPT(๐), in time poly(|๐ |). We start by providing several definitions
and structural observations that will be helpful in designing the algorithm.
6.6.1 Conflicting sets
Our algorithm uses the notion of conflicting point sets, defined as follows.
Definition 6.12 (Conflicting Sets). Let ๐ and ๐0 be sets of points. We say that ๐ and ๐0 are
conflicting if ๐ โช ๐0 is not satisfied.
The following definition is central to our algorithm.
Definition 6.13 (Top representation). Let ๐ be any set of points. A top representation of ๐, that
we denote by top(๐), is a subset ๐0 โ ๐ of points, obtained as follows: for every column ๐ถ that
contains points from ๐, we add the topmost point of ๐ that lies on ๐ถ to ๐0.
Observation 6.14. Let top(๐) โ ๐ be the top representation of ๐, and let ๐
be a row lying strictly
above all points in ๐. Let ๐ be any set of points lying on row ๐
. Then ๐ก๐๐(๐) is conflicting with
๐ if and only if ๐ is conflicting with ๐.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 56
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
Proof. Assume that ๐ is conflicting with ๐, and let ๐ โ ๐, ๐ โ ๐ be a pair of points, such that no
point of ๐ โช ๐ lies in ๐,๐ \ {๐, ๐}. But then ๐ โ top(๐) must hold, and no point of top(๐) โช ๐ lies
in ๐,๐ \ {๐, ๐}, so top(๐) and ๐ are conflicting. Assume now that top(๐) and ๐ are conflicting,
and let ๐ โ ๐, ๐ โ top(๐) be a pair of points, such that no point of ๐ โช top(๐) lies in ๐,๐ \ {๐, ๐}.
But then no point of ๐ โช ๐ lies in ๐,๐ \ {๐, ๐}, and, since top(๐) โ ๐, sets top(๐) and ๐ are
conflicting.
6.6.2 The setup
Let ๐ be the input point set, that is a semi-permutation. We denote by โ = {๐
1 , . . . , ๐
๐ } the set
of all active rows for ๐, and we assume that they are indexed in their natural bottom-to-top
order. We denote by ๐ = {๐ถ1 , . . . , ๐ถ ๐ } the set of all active columns of ๐, and we assume that
they are indexed in their natural left-to-right order. We also denote ๐ = {๐ 1 , . . . , ๐ ๐ }, where for
all 1 โค ๐ โค ๐, ๐ ๐ is the unique point of ๐ lying on row ๐
๐ . For an index 1 โค ๐ก โค ๐, we denote by
โ โค๐ก = {๐
1 , . . . , ๐
๐ก }, and we denote by ๐โค๐ก = {๐ 1 , . . . , ๐ ๐ก }.
Note that, if ๐ is a feasible solution to instance ๐, then for all 1 โค ๐ก โค ๐, the set ๐โค๐ก โช ๐โค๐ก
of points must be satisfied (here ๐โค๐ก is the set of all points of ๐ lying on rows of โ โค๐ก .) Our
dynamic programming-based algorithm constructs the optimal solution row-by-row, using this
observation. We use height profiles, that we define next, as the โstatesโ of the dynamic program.
A height profile ๐ assigns, to every column ๐ถ ๐ โ ๐, a value ๐(๐ถ ๐ ) โ {1, . . . , ๐, โ}. Let ฮ be the set
of all possible height profiles, so |ฮ | โค ๐ ๐(๐) . For a profile ๐ โ ฮ , we denote by ๐(๐) the largest
value of ๐(๐ถ ๐ ) for any column ๐ถ ๐ โ ๐ that is not โ. Given a height profile ๐, let ๐(๐) โ ๐ be the
set of columns ๐ถ ๐ with ๐(๐ถ ๐ ) < โ, and let ๐ 0(๐) = ๐ \ ๐(๐). We can then naturally associate an
ordering ๐๐ of the columns in ๐(๐) with ๐ as follows: for columns ๐ถ ๐ , ๐ถ ๐ โ ๐(๐), ๐ถ ๐ appears
before ๐ถ ๐ in ๐ iff either (i) ๐(๐ถ ๐ ) < ๐(๐ถ ๐ ); or (ii) ๐(๐ถ ๐ ) = ๐(๐ถ ๐ ) and ๐ < ๐.
Consider now any point set ๐, where every point lies on a column of ๐. Let ๐0 = top(๐), and
let ๐(๐) denote the ordering of the points in ๐0, such that ๐ appears before ๐ 0 in ๐ iff either (i)
๐.๐ฆ < ๐ 0 .๐ฆ; or (ii) ๐.๐ฆ = ๐ 0 .๐ฆ and ๐.๐ฅ < ๐ 0 .๐ฅ. Consider now any profile ๐ โ ฮ . We say that point
set ๐ is consistent with profile ๐ (see Figure 8 for an illustration) iff the following hold:
โข For every column ๐ถ ๐ โ ๐, if ๐(๐ถ ๐ ) = โ, then no point of ๐ lies on ๐ถ ๐ ; and
โข For all 1 โค ๐ โค |๐0 |, the ๐th point in ๐(๐) lies on the ๐th column of ๐๐ .
6.6.3 Our DP
Consider some integer ๐ก : 1 โค ๐ก โค ๐ (viewed as a row index) and some height profile ๐; we
define ๐(๐) as the largest value of ๐(๐ถ ๐ ) for ๐ถ ๐ โ ๐ that is not โ. We say that ๐ is a legal profile
for time ๐ก iff ๐(๐) โค ๐ก, and, if ๐ถ ๐ is the column containing the input point ๐ ๐ก , then ๐(๐ถ ๐ ) = ๐(๐)
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 57
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
Figure 8: An illustration of height profile that is consistent with a set ๐ of points. The set
top(๐) is shown by dark points. The height profile is ๐(๐ถ1 ) = 1, ๐(๐ถ2 ) = ๐(๐ถ5 ) = 2 and
๐(๐ถ3 ) = โ ๐ (๐ถ4 ) = 3.
(that is, column ๐ถ ๐ has the largest value ๐(๐ถ ๐ ) that is not โ; we note that it is possible that other
columns ๐ถ ๐ โ ๐ถ ๐ also have ๐(๐ถ ๐ ) = ๐(๐)).
For every integer 1 โค ๐ก โค ๐, and every height profile ๐ that is legal for ๐ก, there is an entry ๐[๐ก, ๐]
in the dynamic programming table. The entry is supposed to store the minimum-cardinality set
๐ of points with the following properties:
โข ๐โค๐ก โ ๐;
โข all points of ๐ lie on rows ๐
1 , . . . , ๐
๐ก ;
โข ๐ is a satisfied point set; and
โข ๐ is consistent with ๐.
Clearly, there number of entries in the dynamic programming table is bounded by ๐๐ ๐(๐) . We
fill out the entries in the increasing order of the index ๐ก.
We start with ๐ก = 1. Consider any profile ๐ that is legal for time ๐ก. Recall that for every column
๐ถ ๐ โ ๐, ๐(๐ถ ๐ ) โ {1, โ} must hold, and moreover, if ๐ถ ๐ is the unique column containing the
point ๐ 1 โ ๐, then ๐(๐ถ ๐ ) = 1 must hold. We let ๐[1, ๐] contain the following set of points: for
every column ๐ถ ๐ โ ๐ with ๐(๐ถ ๐ ) = 1, we add the point lying in the intersection of column ๐ถ ๐
and row ๐
1 to the point set stored in ๐[๐ก, ๐]. It is immediate to verify that the resulting point set
is consistent with ๐, it is satisfied, it contains ๐โค1 = {๐ 1 }, and it is the smallest-cardinality point
set with these properties.
We now assume that for some ๐ก โฅ 1, we have computed correctly all entries ๐[๐ก 0 , ๐0] for all
1 โค ๐ก 0 โค ๐ก, and for all profiles ๐0 legal for ๐ก 0. We now fix some profile ๐ that is legal for ๐ก + 1, and
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 58
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
show how to compute entry ๐[๐ก + 1, ๐].
Let ๐ = ๐(๐) (recall that this is the largest value of ๐(๐ถ ๐ ) that is not โ), and let ๐1 โ ๐ be the
set of all columns ๐ถ ๐ with ๐(๐ถ ๐ ) = ๐. Recall that, if ๐ถ ๐ is the column containing the input point
๐ ๐ก+1 , then ๐ถ ๐ โ ๐1 must hold. Let ๐ be the set of |๐1 | points that lie on the intersection of the
row ๐
๐ก+1 and the columns in ๐1 .
Consider now any profile ๐0 that is legal for ๐ก, and let ๐ห = ๐[๐ก, ๐0]. Denote ๐ห 0 = top(๐).ห We say
that profile ๐ is a candidate profile if (i) ๐ is legal for ๐ก; (ii) the point sets ๐, ๐ห do not conflict;
0 0 0
(iii) ๐ 0(๐0) โ ๐ 0(๐) โช ๐1 ; and (iv) if we discard from ๐๐ and from ๐๐0 the columns of ๐1 , then
the two orderings are defined over the same set of columns and they are identical. We select a
candidate profile ๐0 that minimizes |๐[๐ก, ๐0]|, and let ๐ = ๐ห โช ๐, where ๐ห is the point set stored
in ๐[๐ก, ๐0]. We then set ๐[๐ก + 1, ๐] = ๐.
We now verify that set ๐ has all required properties. If the entry ๐[๐ก, ๐0] was computed correctly,
then point set ๐ห is satisfied. Since top(๐)
ห and ๐ are not conflicting, from Observation 6.14
neither are ๐ห and ๐. Therefore, set ๐ is satisfied. If the entry ๐[๐ก, ๐0] was computed correctly,
then ๐โค๐ก โ ๐.ห Since ๐ ๐ก+1 โ ๐, we get that ๐โค(๐ก+1) โ ๐.
Next, we show that ๐ is consistent with the profile ๐. Let ๐0 = top(๐), and consider the ordering
๐(๐) of the points in ๐0. It is easy to verify that the last |๐| points in this ordering are precisely
the points of ๐. The remaining points in this ordering can be obtained from the point set ๐ห 0, by
first ordering them according to ordering ๐(๐), ห and then deleting all points lying on columns of
๐1 . From the definition of candidate profiles, it is easy to verify that for all 1 โค ๐ โค |๐0 |, the ๐th
point in ๐(๐) lies on the ๐th column of ๐๐ . Therefore, ๐ is consistent with profile ๐.
Lastly, it remains to show that the cardinality of ๐ is minimized among all sets with the above
properties. Let ๐ โ be the point set that contains ๐โค๐ก+1 , is satisfied, is consistent with profile ๐,
with every point of ๐ โ lying on rows ๐
1 , . . . , ๐
๐ก+1 , such that |๐ โ | is minimized among all such
sets. It is easy to verify that the set of points of ๐ โ lying on row ๐
๐ก+1 must be precisely ๐. This
is since point ๐ ๐ก+1 must belong to ๐ โ , and so every column ๐ถ ๐ with ๐(๐ถ ๐ ) = ๐(๐) must have a
point lying on the intersection of ๐ถ ๐ and ๐
๐ก+1 in ๐ โ . Let ๐ห = ๐ โ \ ๐. Clearly, ๐ห is satisfied, all
points of ๐ห lie on rows ๐
1 , . . . , ๐
๐ก , and ๐โค๐ก โ ๐.
ห Moreover, there is no conflict between top(๐)ห
and ๐.
We define a new height profile ๐0 as follows: for every column ๐ถ ๐ โ ๐, if no point of ๐ห lies on
๐ถ ๐ , then ๐0(๐ถ ๐ ) = โ. Otherwise, let ๐ be the unique point in ๐ห 0 that lies on ๐ถ ๐ , and assume that
it lies on row ๐
๐ก 0 . Then we set ๐0(๐ถ ๐ ) = ๐ก 0. Notice that ๐ 0(๐0) โ ๐ 0(๐) โช ๐1 , and, if we discard
from ๐๐ and from ๐๐0 the columns of ๐1 , then the two orderings are defined over the same set of
columns and they are identical.
It is easy to verify that the resulting profile ๐0 must be legal for ๐ก. Therefore, profile ๐0 was
considered by the algorithm. Since ๐ห 0 and ๐ are not conflicting, it is easy to verify that for any
other set ๐ห of points that lie on rows ๐
1 , . . . , ๐
๐ก and are consistent with profile ๐0, set top(๐)
ห
does not conflict with ๐. Therefore, ๐ must be a candidate profile for ๐. We conclude that
0
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 59
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
ห and |๐[๐ก, ๐]| โค |๐[๐ก, ๐0]| + |๐| = |๐ โ |, so |๐| โค |๐ โ | must hold.
|๐[๐ก, ๐0]| โค | ๐|,
The output of the algorithm is a set ๐[๐, ๐] \ ๐ of smallest cardinality among all profiles ๐ โ ฮ
that are consistent with ๐. It is immediate to verify that this is a feasible and optimal solution
for ๐.
As observed before, the number of entries in the dynamic programming table is ๐ ยท ๐ ๐(๐) , and
computing each entry takes time ๐ ๐(๐) . Therefore, the total running time of the algorithm is
bounded by ๐ ยท ๐ ๐(๐) .
7 An ๐(log log ๐)-competitive online algorithm
In this section we extend the ๐(log log ๐)-approximation algorithm from the previous section
to the online setting, completing the proof of Theorem 1.2. To this end, the recursive algorithm
is not quite convenient to work with. In Subsection 7.1, we present an equivalent iterative
description of our algorithm. In Subsection 7.2, we slightly modify the solution ๐ that the
algorithm returns to obtain another solution ๐ห that is more friendly for the online setting, before
presenting the final online algorithm in Subsection 7.3.
7.1 Unfolding the recursion
Let ๐ be an input set of points that is semi-permutation, with |๐ | = ๐, and ๐(๐) = ๐. Let ๐ be a
balanced partitioning tree of height ๐ป = ๐(log ๐) for ๐.
We now construct another tree ๐
, that is called a recursion tree, and which is unrelated to the
tree ๐. Every vertex ๐ of the tree ๐
is associated with an instance โ(๐) of Min-Sat that arose
during the recursive execution of Algorithm RecursiveBST(๐ , ๐, ๐), with ๐ = 1. Specifically,
for the root ๐ of the tree ๐
, we let โ(๐) = ๐. For every vertex ๐ of the tree ๐
, if Algorithm
RecursiveBST(๐ , ๐, ๐), when called for instance โ(๐), constructed instances โ1 , . . . , โ๐ง (recall
that one of these instances is a compressed instance, and the remaining instances are strip
instances), then vertex ๐ has ๐ง children in tree ๐
, each of which is associated with one of these
instances.
For a vertex ๐ โ ๐(๐
), let ๐(๐) be the number active columns in the instance โ(๐). Recall that
instance โ(๐) corresponds to some subtree of the partitioning tree ๐, that we denote by ๐๐ . For
all ๐ โฅ 0, let ฮ0๐ be the set of all vertices of the tree ๐
that lie at distance exactly ๐ from the root of
๐
. We say that the vertices of ฮ0๐ belong to the ๐th layer of ๐
. Notice that, if vertex ๐ lies in the
๐th layer of ๐
, then the height of the corresponding tree ๐๐ is bounded by ๐ป ยท (2/3)๐ (the constant
๐ is split in its middle layer, each of
2/3 is somewhat arbitrary and is used because, when a tree 0
0
the resulting subtrees has height at most height(๐ )/2 + 1 โค 2๐ป/3). Recall that the recursion
terminates once we obtain instances whose corresponding partitioning trees have height 1. It is
then easy to verify that the height of the recursion tree ๐
is bounded by ๐(log log ๐).
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 60
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
Figure 9: An illustration of the families ๐ฏ๐ . Notice that ๐ฏ1 contains 5 trees, each having height 2.
Consider now some layer ฮ๐ of the recursion tree ๐
. We let ๐ฏ๐ be the collection of all subtrees of
the partitioning tree ๐ corresponding to the vertices of ฮ๐ , so ๐ฏ๐ = ๐๐ | ๐ โ ฮ๐ . Recall that all
trees in ๐ฏ๐ have height at most ๐ป ยท (2/3)๐ .
Notice that ๐ฏ0 = {๐}. Let ๐ = {๐ฃ 1 , . . . , ๐ฃ ๐ } be the middle layer of ๐. Then ๐ฏ1 = ๐๐ฃ1 , . . . , ๐๐ฃ ๐ , ๐๐ .
Set ๐ฏ2 is similarly obtained by subdividing every tree in ๐ฏ1 , and so on. (See Figure 9 for an
illustration. ) The construction of the tree sets ๐ฏ๐ can be described using the following process:
โข Start from ๐ฏ0 = {๐}.
โข For ๐ = 1, . . . , ๐ท, if some tree in ๐ฏ๐โ1 has height greater than 1, then construct the set ๐ฏ๐ of
n everyotree ๐ โ ๐ฏ๐ whose height is greater than 1, consider the split
trees as follows: For 0
e by the (boundaries of) middle-layer strips. Notice that ๐
partitioning trees {๐๐ }, ๐ e is
rooted at the root of ๐ 0 and each ๐๐ at a leaf of ๐.
e These subtrees are added into ๐ฏ๐ .
The following observation is immediate.
Observation 7.1. For each 1 โค ๐ โค ๐ท, ๐ 0 โ๐ฏ๐ ๐(๐ 0) = ๐(๐), and for each pair ๐ 0 , ๐ 00 โ ๐ฏ๐ of trees,
ร
either ๐(๐ 0) โฉ ๐(๐ 00) = โ
or the root of one of these trees is a leaf of the other tree.
7.1.1 Boxes
Fix an index 1 โค ๐ โค ๐ท, and consider any tree ๐ 0 โ ๐ฏ๐ . Denote the number of leaves by ๐,
and let ๐ฃ 1 , . . . , ๐ฃ ๐ be the leaves of ๐ 0. If ๐ฃ is the root vertex of the tree ๐ 0, then we can view ๐ 0
as defining a hierarchical partitioning scheme of the strip ๐(๐ฃ), until we obtain the partition
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 61
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
(๐(๐ฃ 1 ), ๐(๐ฃ 2 ), . . . , ๐(๐ฃ ๐ )) of ๐(๐ฃ). We define a collection of ๐ 0-boxes as follows. Let ๐ 0 = ๐ โฉ ๐(๐ฃ)
be the set of all points lying in strip ๐(๐ฃ). Assume that ๐ 0 = {๐ 1 , ๐2 , . . . , ๐ ๐0 }, where the points
are indexed in the increasing order of their ๐ฆ-coordinates.
We now iteratively partition the point set ๐ 0 into boxes, where each box is a consecutive set of
points of ๐ 0. Let ๐ฃ ๐ be the leaf vertex of ๐ 0, such that ๐ 1 โ ๐(๐ฃ ๐ ), and let ๐1 be the largest index,
such that all points ๐ 1 , . . . , ๐ ๐1 lie in ๐(๐ฃ ๐ ). We then then define a box ๐ต1 = {๐ 1 , ๐2 , . . . , ๐ ๐1 }.
We discard the points ๐ 1 , . . . , ๐ ๐1 , and continue this process to define ๐ต2 (starting from point
๐ ๐1 + 1), and so on, until every point of ๐ 0 belongs to some box.
We let โฌ(๐ 0) = ๐ต1 , ๐ต2 , . . . , ๐ต ๐ง(๐ 0) be the resulting partition of the points in ๐ 0, where we refer
to each set ๐ต ๐ as a ๐ 0-box, or just a box. For each box ๐ต0 โ โฌ(๐ 0), the lowest and the highest rows
containing points of ๐ต0 are denoted by first(๐ต0) and last(๐ต0) respectively.
7.1.2 Projections of points
Recall that the solution that our recursive algorithm returns is ๐-special, that is, the points that
participate in the solution lie on the active rows of ๐ and on ๐-auxiliary columns. Let ๐ be a
feasible solution obtained by our algorithm RecursiveBST(๐, ๐, ๐), where ๐ = 1. Notice the
every point in ๐ is obtained by โprojectingโ some input point ๐ โ ๐ to the boundary of some
strip ๐(๐ฃ) for ๐ฃ โ ๐(๐), where strip ๐(๐ฃ) contains ๐. For each point ๐ โ ๐ and node ๐ฃ โ ๐(๐) of
the partitioning tree, such that ๐ โ ๐(๐ฃ), we define the set proj(๐, ๐ฃ) to contain two points on
the same row as ๐, that lie on the left and right boundaries of ๐(๐ฃ), respectively. We denote
by ๐๐,๐ฃ the set that contain the two points proj(๐, ๐ฃ) if our algorithm adds these two points
to the solution. Since all points of ๐ lie on distinct rows, for any two points ๐ โ ๐ 0, for any
pair ๐ฃ, ๐ฃ 0 โ ๐(๐) of vertices, proj(๐, ๐ฃ) โฉ proj(๐ 0 , ๐ฃ 0) = โ
. We can now write the solution ๐ as
๐ = ๐โ๐ ๐ฃโ๐(๐) ๐๐,๐ฃ . The following lemma characterizes the points of ๐ in terms of boxes.
ร ร
Lemma 7.2. For every point ๐ โ ๐ and every node ๐ฃ โ ๐(๐) of the partitioning tree, |๐๐,๐ฃ | = 2 if and
only if there is an index 1 โค ๐ โค ๐ท, and a subtree ๐ 0 โ ๐ฏ๐ , such that (i) ๐ is the first or the last point of its
๐ 0-box; (ii) ๐ฃ lies in the middle layer of ๐ 0; and (iii) ๐(๐ฃ) contains ๐.
Proof. Let 1 โค ๐ โค ๐ท be an index, and let ๐ 0 โ ๐ฏ๐ be the corresponding partitioning tree.
We denote the corresponding point set by ๐ 0. Let ๐ฃ 1 , . . . , ๐ฃ ๐ be the leaf vertices of ๐ 0, and
let ๐ข1 , . . . , ๐ข๐ be the vertices lying in the middle layer of ๐ 0. The only points added to the
solution when instance ๐ 0 is processed are the following: for every 1 โค ๐ โค ๐, for every point
๐ โ ๐ 0 โฉ ๐(๐ข ๐ ), we add the two copies of ๐ to the boundaries of ๐(๐ข ๐ ). In subsequent, or in
previous iterations, we may add points to boundaries of ๐(๐ข ๐ ), but we will never add two copies
of the same input point to both boundaries of ๐(๐ข ๐ ). Therefore, if |๐๐,๐ฃ | = 2, then there must
be an index ๐, and a tree ๐ 0 โ ๐ฏ๐ , such that ๐ฃ lies in the middle layer of ๐ 0, and ๐(๐ฃ) contains ๐.
Observe that for every ๐ 0-box ๐ต, instance ๐ 0 only contains the first and the last point of ๐ต; all
remaining points are redundant for ๐ 0, and such points are not projected to the boundaries of
their strips. Therefore, ๐ must be the first or the last point of its ๐ 0-box.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 62
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
7.1.3 An equivalent view of our algorithm
We can think of our algorithm as follows. First, we compute all families ๐ฏ0 , ๐ฏ1 , . . . , ๐ฏ๐ท of trees,
and for each tree ๐ 0 in each family ๐ฏ๐ , all ๐ 0-boxes. For each point ๐ โ ๐, for each vertex ๐ฃ โ ๐(๐)
of the partitioning tree ๐, such that ๐ โ ๐(๐ฃ), we add the projection points proj(๐, ๐ฃ) to the
solution, depending on whether there exists an index ๐ โ {0, 1, . . . , ๐ท} and a tree ๐ 0 โ ๐ฏ๐ , such
that ๐ฃ lies in the middle layer ๐๐ 0 of ๐ 0, and whether ๐ is the first or last point of its ๐ 0-box.
Notice that in the online setting, when the point ๐ arrives, we need to be able to immediately
decide which copies of ๐ to add to the solution. Since the trees in the families ๐ฏ0 , ๐ฏ1 , . . . , ๐ฏ๐ท are
known in advance, and we discover, for every vertex ๐ฃ โ ๐(๐) whether ๐ โ ๐(๐ฃ) immediately
when ๐ arrives, the only missing information, for every relevant tree ๐ 0, is whether vertex ๐ is
the first or the last vertex in its ๐ 0-box. In fact it is easy to check whether it is the first vertex
in its ๐ 0-box, but we will not discover whether it is the last vertex in its ๐ 0-box until the next
iteration, at which point it is too late to add points to the solution that lie in the row of ๐.
In order to avoid this difficulty, we slightly modify the instance and the solution.
7.2 Online-friendly solutions
In this section we slightly modify both the input set of points and the solutions produced by our
algorithm, in order to adapt them to the online setting.
7.2.1 Modifying the instance
Let ๐ = {๐ 1 , . . . , ๐ ๐ } be the input setof points, where for all 1 โค ๐ โค ๐, the ๐ฆ-coordinate of ๐ ๐ is
๐. We produce a new instance ๐ 0 = ๐ 0๐ , ๐ 00๐ | 1 โค ๐ โค ๐ , as follows: for all 1 โค ๐ โค ๐, we let ๐ 0๐
and ๐ 00๐ be points whose ๐ฆ-coordinates are (2๐ โ 1) and 2๐, respectively, and whose ๐ฅ-coordinate
is the same as that of ๐ ๐ . We refer to ๐ 0๐ and to ๐ 00๐ as copies of ๐ ๐ .
Clearly, |๐ 0 | = 2|๐ |, and it is easy to verify that OPT(๐ 0) โค 2OPT(๐). Indeed, if we let ๐ be a
solution for ๐, we can construct a solution ๐ 0 for ๐ 0, by creating, for every point ๐ โ ๐, two
copies ๐ 0 and ๐ 00, that are added to rows with ๐ฆ-coordinates 2๐.๐ฆ โ 1 and 2๐.๐ฆ respectively.
For convenience, we denote ๐ฏ = ๐ท ๐=0 ๐ฏ๐ . Notice that, for every tree ๐ โ ๐ฏ , for every point ๐ ๐ of
0
ร
the original input ๐, copy ๐ 0๐ of ๐ ๐ may never serve as the last point of a ๐ 0-box, and copy ๐ 00๐ of
๐ ๐ may never serve as the first point of a ๐ 0-box.
7.2.2 Modifying the solution
Let ๐ be the solution that our ๐(log log ๐)-approximation algorithm produces for the new
instance ๐ 0. For convenience, for all 1 โค ๐ โค 2๐, we denote by ๐
๐ the row with ๐ฆ-coordinate ๐.
Notice that all points of ๐ lying on a row ๐
2๐โ1 are projections of the point ๐ 0๐ . Since this point
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 63
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
may only serve as the first point of a ๐ 0-box for every tree ๐ 0 โ ๐ฏ , when point ๐ 0๐ arrives online,
we can immediately compute all projections of ๐ 0๐ that need to be added to the solution. All
points of ๐ lying on row ๐
2๐ are projections of the point ๐ 00๐ . This point may only serve as the
last point of a ๐ 0-box in a tree ๐ 0 โ ๐ฏ . But we cannot know whether ๐ 00๐ is the last point in its
๐ 0-box until we see the next input point. Motivated by these observations, we now modify the
solution ๐ as follows.
We perform ๐ iterations. In iteration ๐, we consider the row ๐
2๐ . If no point of ๐ lies on row ๐
2๐ ,
then we continue to the next iteration. Otherwise, we move every point of ๐ that lies on row ๐
2๐
to row ๐
2๐+1 (that is, one row up). Additionally, we add another copy ๐ 000๐
of point ๐ ๐ to row ๐
2๐ ,
while preserving its ๐ฅ-coordinate.
In order to show that the resulting solution is a feasible solution to instance ๐ 0, it is sufficient to
show that the solution remains feasible after every iteration. Let ๐๐ be the solution ๐ obtained
before the ๐th iteration, and let ๐ ๐ = ๐ 0 โช ๐๐ . We can obtain the new solution ๐๐+1 equivalently
as follows. First, we collapse the rows ๐
2๐+1 and ๐
2๐ for the set ๐ ๐ of points into the row ๐
2๐+1 ,
obtaining a new set ๐0๐ of points that is guaranteed to be satisfied. Notice that now both row
๐
2๐+1 and row ๐
2๐โ1 contain a point at ๐ฅ-coordinate (๐ ๐ ).๐ฅ, while row ๐
2๐ contains no points.
Therefore, if we add to ๐0๐ a point with ๐ฅ-coordinate (๐ ๐ ).๐ฅ, that lies at row ๐
2๐ , then the resulting
set of points, that we denote by ๐ ๐+1 remains satisfied. But it is easy to verify that ๐ ๐+1 = ๐ 0 โช ๐๐+1 ,
where ๐๐+1 is the solution obtained after iteration ๐. We denote by ๐ 0 the final solution obtained
by this transformation of ๐. It is easy to see that |๐ 0 | โค 2|๐| โค ๐(log log ๐)OPT(๐).
7.3 The final online algorithm
Let ๐ = {๐ 1 , . . . , ๐ ๐ } be an input set of points. We will describe the online algorithm that
produces a feasible solution to instance ๐. This algorithm would mimic the behavior of the
point set ๐ 0 as described earlier.
Initially, the algorithm computes the collection ๐ฏ of trees before any input arrives. Now, in
iteration ๐, when input ๐ ๐ arrives, we compute ๐น๐ผ๐
๐๐(๐):
ร ร
๐น๐ผ๐
๐๐(๐) = proj(๐ ๐ , ๐ฃ)ยฎ
ยฉ ยช
ยญ
๐ 0 โ๐ฏ :๐ ๐ is first of a ๐ 0 -box ยซ๐ฃ:๐ฃ is middle layer of ๐ 0 , and ๐(๐ฃ) contains ๐ ๐ ยฌ
We also compute ๐ฟ๐ด๐๐(๐ โ 1):
ร ร
๐ฟ๐ด๐๐(๐ โ 1) = proj(๐ ๐โ1 , ๐ฃ)ยฎ
ยฉ ยช
ยญ
๐ 0 โ๐ฏ :๐ ๐โ1 is last of a ๐ 0 -box ยซ๐ฃ:๐ฃ is middle layer of ๐ 0 and ๐(๐ฃ) contains ๐ ๐โ1 ยฌ
We add copies of ๐น๐ผ๐
๐๐(๐) and ๐ฟ๐ด๐๐(๐ โ 1), and a copy of ๐ ๐โ1 points on row ๐. It is easy to
verify that the resulting solution is precisely the solution obtained after collapsing every two
consecutive rows in ๐ 0 (as discussed previously). Therefore the solution is feasible and has cost
at most |๐ 0 | โค ๐(log log ๐)OPT.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 64
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
8 Wilber and Guillotine bounds
In this section, we provide an alternative, geometric proof of the fact that WB(๐) โค 2OPT(๐),
which can be extended to the Guillotine bound. The original proof of Wilber [29] is done in the
tree view.
8.1 Wilber bound
It is sufficient to prove that, if ๐ is a semi-permutation, and ๐ is any partitioning tree for ๐, then
WB๐ (๐) โค 2OPT(๐).
We prove this claim by induction on the height of ๐. The base case, when the height of ๐ is 0, is
obvious: there is only one active column, and so WB๐ (๐) = OPT(๐) = 0.
We now consider the inductive step. Let ๐ be any point set that is a semi-permutation, and let ๐
be any partitioning tree for ๐, such that the height of ๐ is at least 1. Let ๐ฃ be the root vertex of ๐,
๐ฟ = ๐ฟ(๐ฃ) the line that ๐ฃ owns, and let ๐ฃ ๐ฟ , ๐ฃ ๐
be the two children of ๐ฃ. We assume w.l.o.g. that
the strip ๐(๐ฃ ๐ฟ ) lies to the left of ๐(๐ฃ ๐
). We denote ๐(๐ฃ) = ๐ต โ the bounding box of the instance,
๐(๐ฃ ๐ฟ ) = ๐ ๐ฟ , ๐(๐ฃ ๐
) = ๐ ๐
, and we also denote ๐ ๐ฟ = ๐ โฉ ๐ ๐ฟ , ๐ ๐
= ๐ โฉ ๐ ๐
. Lastly, we let ๐ ๐ฟ and ๐ ๐
be the subtrees of ๐ rooted at ๐ฃ ๐ฟ and ๐ฃ ๐
, respectively. We prove the following claim.
Claim 8.1.
OPT(๐) โฅ OPT(๐ ๐ฟ ) + OPT(๐ ๐
) + cost(๐ฃ)/2.
Notice that, if the claim is correct, then we can use the induction hypothesis on ๐ ๐ฟ and ๐ ๐
with
the trees ๐ ๐ฟ and ๐ ๐
respectively, to conclude that:
1 1
OPT(๐) โฅ (WB๐ ๐ฟ (๐๐ฟ ) + WB๐ ๐
(๐๐
) + cost(๐ฃ)) = WB๐ (๐).
2 2
Therefore, in order to complete the proof of Claim 2.7, it is enough to prove Claim 8.1.
Proof. Claim 8.1 Let ๐ be an optimal solution to instance ๐. We can assume w.l.o.g. that ๐ is a
canonical solution, so no point of ๐ lies on the line ๐ฟ. Let ๐ ๐ฟ , ๐ ๐
be the subsets of points of ๐
that lie to the left and to the right of the line ๐ฟ, respectively.
Let โ ๐ฟ be the set of all rows ๐
, such that (i) no point of ๐ ๐ฟ lies on ๐
, and (ii) some point of ๐ ๐ฟ
lies on ๐
. We define a set โ ๐
of rows similarly for instance ๐ ๐
. The crux of the proof is the
following observation.
Observation 8.2.
|โ ๐ฟ | + |โ ๐
| โฅ cost(๐ฃ)/2.
Before we prove Observation 8.2, we show that Claim 8.1 follows from it. In order to do so, we
will define a new feasible solution ๐ห ๐ฟ for instance ๐ ๐ฟ , containing at most |๐ ๐ฟ | โ |โ ๐ฟ | points,
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 65
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
and similarly, we will define a new feasible solution ๐ห ๐
for instance ๐ ๐
, containing at most
|๐ ๐
| โ |โ ๐
| points. This will prove that OPT(๐ ๐ฟ ) โค |๐ ๐ฟ | โ |โ ๐ฟ | and OPT(๐ ๐
) โค |๐ ๐
| โ |โ ๐ฟ |,
so altogether, OPT(๐ ๐ฟ ) + OPT(๐ ๐
) โค |๐| โ |โ ๐ฟ | โ |โ ๐
| โค OPT(๐) โ cost(๐ฃ)/2, thus proving
Claim 8.1.
We now show how to construct the solution ๐ห ๐ฟ for instance ๐ ๐ฟ . The solution ๐ห ๐
for instance ๐ ๐
is constructed similarly.
In order to construct the solution ๐ห ๐ฟ , we start with the solution ๐ ๐ฟ , and then gradually modify
it over the course of |โ ๐ฟ | iterations, where in each iteration we reduce the number of points in
the solution ๐ ๐ฟ by at least 1, and we eliminate at most one row from โ ๐ฟ . In order to execute an
iteration, we select two rows ๐
, ๐
0, with the following properties:
โข Row ๐
contains a point of ๐ ๐ฟ ;
โข Row ๐
0 contains a point of ๐ ๐ฟ and it contains no points of ๐ ๐ฟ ; and
โข No point of ๐ ๐ฟ โช ๐ ๐ฟ lies strictly between rows ๐
and ๐
0.
Note that, if โ ๐ฟ โ โ
, such a pair of rows must exist. We then collapse the row ๐
0 into the row ๐
,
obtaining a new modified solution to instance ๐ ๐ฟ (we use Observation 2.4). We claim that the
number of points in the new solution decreases by at least 1. In order to show this, it is sufficient
to show that there must be two points ๐ โ ๐
, ๐ 0 โ ๐
0 with the same ๐ฅ-coordinates; after the two
rows are collapsed, these two points are mapped to the same point. Assume for contradiction
that no such two points exist. Let ๐ โ ๐
, ๐ 0 โ ๐
0 be two points with smallest horizontal distance.
Then it is easy to see that no point of ๐ ๐ฟ โช ๐ ๐ฟ lies in the rectangle ๐,๐0 , contradicting the fact
that ๐ ๐ฟ is a feasible solution for ๐ ๐ฟ .
In order to complete the proof of Claim 8.1, it is now enough to prove Observation 8.2.
Proof. Observation 8.2 We denote ๐ = {๐ 1 , . . . , ๐ ๐ }, where the points are indexed in the
increasing order of their ๐ฆ-coordinates. Recall that a pair (๐ ๐ , ๐ ๐+1 ) of points is a crossing, if the
two points lie on opposite sides of the line ๐ฟ. We say that it is a left-to-right crossing if ๐ ๐ lies to
the left of ๐ฟ, and we say that it is a right-to-left crossing otherwise. Clearly, either at least half
the crossings of ๐ฟ are left-to-right crossings, or at least half the crossings of ๐ฟ are right-to-left
crossings. We assume w.l.o.g. that it is the former. Let ฮ denote the set of all left-to-right
crossings of ๐ฟ, so |ฮ | โฅ cost(๐ฃ)/2. Notice that every point of ๐ participates in at most one
crossing in ฮ . We will associate, to each crossing (๐ ๐ , ๐ ๐+1 ) โ ฮ , a unique row in โ ๐ฟ โช โ ๐
. This
will prove that |โ ๐ฟ | + |โ ๐
| โฅ |ฮ | โฅ cost(๐ฃ)/2.
Consider now some crossing (๐ ๐ , ๐ ๐+1 ). Assume that ๐ ๐ lies in row ๐
, and that ๐ ๐+1 lies in row
๐
0. Let โ ๐ be a set of all rows lying between ๐
and ๐
0, including these two rows. We will show
that at least one row of โ ๐ lies in โ ๐ฟ โช โ ๐
. In order to do so, let ๐ป be the closed horizontal strip
whose bottom and top boundaries are ๐
and ๐
0, respectively. Let ๐ป ๐ฟ be the area of ๐ป that lies to
the left of the line ๐ฟ, and that excludes the row ๐
โ the row containing the point ๐ ๐ , that also
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 66
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
lies to the left of ๐ฟ. Similarly, let ๐ป ๐
be the area of ๐ป that lies to the right of the line ๐ฟ, and that
excludes the row ๐
0. Notice that, if any point ๐ฆ โ ๐ ๐ฟ lies in ๐ป ๐ฟ , that the row containing ๐ฆ must
belong to โ ๐ฟ . Similarly, if any point ๐ฆ 0 โ ๐ ๐
lies in ๐ป ๐
, then the row containing ๐ฆ 0 belongs to
โ ๐
. Therefore, it is now sufficient to show that either ๐ป ๐ฟ contains a point of ๐ ๐ฟ , or ๐ป ๐
contains
a point of ๐ ๐
. Assume for contradiction that this is false. Let ๐ โ ๐ ๐ฟ โช ๐ ๐ฟ be the point lying on
the row ๐
furthest to the right (such a point must exist because we can choose ๐ = ๐ ๐ ). Similarly,
let ๐ 0 โ ๐ ๐
โช ๐ ๐
be the point lying on the row ๐
0 furthest to the left (again, such a point must
exist because we can choose ๐ 0 = ๐ ๐+1 .) But if ๐ป ๐ฟ contains no points of ๐ ๐ฟ , and ๐ป ๐
contains no
points of ๐ ๐
, then no points of ๐ โช ๐ lie in the rectangle ๐,๐0 , and so the pair (๐, ๐ 0) of points is
not satisfied in ๐ โช ๐, a contradiction.
8.2 Guillotine bound
In this section we prove Lemma 5.3, by showing that for any point set ๐ that is a permutation,
GB(๐) โค 2OPT(๐). In order to do so, it is enough to prove that, for any point set ๐ that is a
permutation, for any partitioning tree ๐ for ๐, GB๐ (๐) โค 2OPT(๐).
The proof is by induction on the height of ๐, and it is almost identical to the proof of Claim 2.7
for the standard Wilber Bound. When the height of the tree ๐ is 1, then |๐ | = 1, so GB(๐) = 0
and OPT(๐) = 0.
Consider now a partitioning tree ๐ whose height is greater than 1. Let ๐1 , ๐2 be the two subtrees
of ๐, obtained by deleting the root vertex ๐ from ๐. Let (๐1 , ๐2 ) be the partition of ๐ into two
subsets given by the line ๐ฟ(๐), such that ๐1 is a partitioning tree for ๐1 and ๐2 is a partitioning
tree for ๐2 . Notice that, from the definition of the GB bound:
GB๐ (๐) = GB๐1 (๐1 ) + GB๐2 (๐2 ) + cost(๐).
Moreover, from the induction hypothesis, GB๐1 (๐1 ) โค 2OPT(๐1 ) and GB๐2 (๐2 ) โค 2OPT(๐2 ).
Using Claim 8.1 (that can be easily adapted to horizontal partitioning lines), we get that:
OPT(๐) โฅ OPT(๐1 ) + OPT(๐2 ) + cost(๐)/2.
Therefore, altogether we get that:
GB๐ (๐) โค 2OPT(๐1 ) + 2OPT(๐2 ) + cost(๐) โค 2OPT(๐).
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 67
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
References
[1] Georgii Maksimovich Adelโson-Velโskii and Evgenii Mikhailovich Landis: An algorithm
for organization of information. Dokl. Akad. Nauk SSSR (Russian), 146(2):263โ266, 1962.
Math-Net.ru. 2
[2] Rudolf Bayer: Symmetric binary B-trees: Data structure and maintenance algorithms. Acta
Informatica, 1(4):290โ306, 1972. [doi:10.1007/BF00289509] 2
[3] Prosenjit Bose, Karim Douรฏeb, John Iacono, and Stefan Langerman: The power and
limitations of static binary search trees with lazy finger. Algorithmica, 76:1264โ1275, 2016.
Preliminary version in ISAACโ14. [doi:10.1007/s00453-016-0224-x] 3
[4] Parinya Chalermsook, Julia Chuzhoy, and Thatchaphol Saranurak: Pinning down the
strong Wilber 1 bound for binary search trees. In Proc. 23rd Internat. Conf. on Approximation
Algorithms for Combinat. Opt. Probl. (APPROXโ20), pp. 33:1โ21. Schloss DagstuhlโLeibniz-
Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.APPROX/RANDOM.2020.33] 8
[5] Parinya Chalermsook, Mayank Goswami, Lรกszlรณ Kozma, Kurt Mehlhorn, and
Thatchaphol Saranurak: Greedy is an almost optimal deque. In Proc. 17th Symp. on
Algorithms and Data Structures (WADSโ15), pp. 152โ165. Springer, 2015. [doi:10.1007/978-3-
319-21840-3_13] 3
[6] Parinya Chalermsook, Mayank Goswami, Lรกszlรณ Kozma, Kurt Mehlhorn, and
Thatchaphol Saranurak: Pattern-avoiding access in binary search trees. In Proc. 56th
FOCS, pp. 410โ423. IEEE Comp. Soc., 2015. [doi:10.1109/FOCS.2015.32, arXiv:1507.06953]
3, 7
[7] Ranjan Chaudhuri and Hartmut F. Hรถft: Splaying a search tree in preorder takes linear
time. SIGACT News, 24(2):88โ93, 1993. [doi:10.1145/156063.156067] 3
[8] Richard Cole: On the Dynamic Finger Conjecture for splay trees. Part II: The proof. SIAM
J. Comput., 30(1):44โ85, 2000. [doi:10.1137/S009753979732699X] 3
[9] Richard Cole, Bud Mishra, Jeanette Schmidt, and Alan Siegel: On the Dynamic Finger
Conjecture for splay trees. Part I: Splay sorting log ๐-block sequences. SIAM J. Comput.,
30(1):1โ43, 2000. [doi:10.1137/S0097539797326988] 3
[10] Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein: Introduction
to Algorithms. MIT press, 2022. MIT Press. 2
[11] Erik D. Demaine, Dion Harmon, John Iacono, Daniel M. Kane, and Mihai Paฬtraลcu: The
geometry of binary search trees. In Proc. 20th Ann. ACMโSIAM Symp. on Discrete Algorithms
(SODAโ09), pp. 496โ505. SIAM, 2009. ACM DL. 3, 4, 5, 9, 12, 36
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 68
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
[12] Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Paฬtraลcu: Dynamic optimalityโ
almost. SIAM J. Comput., 37(1):240โ251, 2007. Preliminary version in FOCSโ04.
[doi:10.1137/S0097539705447347] 3, 4, 6, 8, 12
[13] Jonathan C. Derryberry and Daniel Dominic Sleator: Skip-splay: Toward achieving the
unified bound in the BST model. In Proc. 11th Symp. on Algorithms and Data Structures
(WADSโ09), pp. 194โ205. Springer, 2009. [doi:10.1007/978-3-642-03367-4_18] 3
[14] Jonathan C. Derryberry, Daniel Dominic Sleator, and Chengwen Chris Wang: A lower
bound framework for binary search trees with rotations. Technical report, CMU-CS-05-187,
2005. Available on authorโs website. 3
[15] Amr Elmasry: On the sequential access theorem and deque conjecture for splay trees.
Theoret. Comput. Sci., 314(3):459โ466, 2004. [doi:10.1016/j.tcs.2004.01.019] 3
[16] George F. Georgakopoulos: Chain-splay trees, or, how to achieve and prove
log log ๐-competitiveness by splaying. Inform. Process. Lett., 106(1):37โ43, 2008.
[doi:10.1016/j.ipl.2007.10.001] 3, 8
[17] Dion Harmon: New Bounds on Optimal Binary Search Trees. Ph. D. thesis, MIT, 2006. MIT. 3
[18] John Iacono: In pursuit of the dynamic optimality conjecture. In A. Brodnik, A. Lรณpez-Ortiz,
V. Raman, and A. Viola, editors, Space-Efficient Data Structures, Streams, and Algorithms,
volume 8066 of LNCS, pp. 236โ250. Springer, 2013. [doi:10.1007/978-3-642-40273-9_16] 4, 6,
12, 26, 36
[19] John Iacono and Stefan Langerman: Weighted dynamic finger in binary search trees. In
Proc. 27th Ann. ACMโSIAM Symp. on Discrete Algorithms (SODAโ16), pp. 672โ691. SIAM,
2016. [doi:10.1137/1.9781611974331.ch49] 3
[20] Lรกszlรณ Kozma: Binary search trees, rectangles and patterns. Ph. D. thesis, Saarland University,
Saarbrรผcken, Germany, 2016. Saarland U. 4, 6
[21] Victor Lecomte and Omri Weinstein: Settling the relationship between Wilberโs bounds
for dynamic optimality. In Proc. 28th Eur. Symp. Algorithms (ESAโ20), pp. 68:1โ21.
Schloss DagstuhlโLeibniz-Zentrum fuer Informatik, 2020. [doi:10.4230/LIPIcs.ESA.2020.68,
arXiv:1912.02858] 4, 5, 7
[22] Caleb C. Levy and Robert E. Tarjan: A new path from splay to dynamic optimality. In
Proc. 30th Ann. ACMโSIAM Symp. on Discrete Algorithms (SODAโ19), pp. 1311โ1330. SIAM,
2019. [doi:10.1137/1.9781611975482.80] 37
[23] Joan M. Lucas: On the competitiveness of splay trees: Relations to the union-find problem.
In Lyle A. McGeoch and Daniel D. Sleator, editors, On-line Algorithms, volume 7 of
DIMACS Ser. in Discrete Math. and Theor. Comp. Sci., pp. 95โ124. Amer. Math. Soc., 1992.
[doi:10.1090/dimacs/007] 3
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 69
PARINYA C HALERMSOOK , J ULIA C HUZHOY, AND T HATCHAPHOL S ARANURAK
[24] Seth Pettie: Splay trees, Davenport-Schinzel sequences, and the Deque Conjecture. In Proc.
19th Ann. ACMโSIAM Symp. on Discrete Algorithms (SODAโ08), pp. 1115โ1124. SIAM, 2008.
[doi:10.5555/1347082.1347204, arXiv:0707.2160] 3
[25] Daniel Dominic Sleator and Robert Endre Tarjan: Self-adjusting binary search trees. J.
ACM, 32(3):652โ686, 1985. Preliminary version in STOCโ83. [doi:10.1145/3828.3835] 3
[26] Rajamani Sundar: On the Deque Conjecture for the splay algorithm. Combinatorica,
12(1):95โ124, 1992. [doi:10.1007/BF01191208] 3
[27] Robert Endre Tarjan: Sequential access in splay trees takes linear time. Combinatorica,
5(4):367โ378, 1985. [doi:10.1007/BF02579253] 3
[28] Chengwen C. Wang, Jonathan C. Derryberry, and Daniel Dominic Sleator: O(log log ๐)-
competitive dynamic binary search trees. In Proc. 17th Ann. ACMโSIAM Symp. on Discrete
Algorithms (SODAโ06), pp. 374โ383. SIAM, 2006. ACM DL. 3, 4, 6, 8
[29] Robert E. Wilber: Lower bounds for accessing binary search trees with rotations. SIAM J.
Comput., 18(1):56โ67, 1989. Preliminary version in FOCSโ86. [doi:10.1137/0218004] 3, 6, 12,
25, 26, 37, 65
AUTHORS
Parinya Chalermsook
Associate professor
Department of Computer Science
Aalto University
Espoo, Finland
chalermsook gmail com
https://sites.google.com/site/parinyachalermsook/
Julia Chuzhoy
Professor
Toyota Technological Institute at Chicago
Chicago, IL, USA
cjulia ttic edu
https://home.ttic.edu/~cjulia/
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 70
P INNING D OWN THE S TRONG W ILBER -1 B OUND FOR B INARY S EARCH T REES
Thatchaphol Saranurak
Assistant professor
University of Michigan
Ann Arbor, MI, USA
thsa umich edu
https://sites.google.com/site/thsaranurak/
ABOUT THE AUTHORS
Parinya Chalermsook is a faculty member at the Department of Computer Science,
Aalto University (Finland). He completed his Ph. D. at The University of Chicago
under the supervision of Julia Chuzhoy and Janos Simon. He was at Max Planck
Institute for Informatics as a postdoc and a senior research scientist from 2013 to
2016. Parinya is broadly interested in algorithms and extremal combinatorics.
When he is not doing mathematics, he enjoys reading about political philosophy.
Julia Chuzhoy is a Professor at the Toyota Technological Institute at Chicago. She
completed her Ph. D. in Technion, Israel, and spent three years as a postdoctoral
scholar at MIT, the University of Pennsylvania and the Institute for Advanced
Study in Princeton. She mainly works on algorithms for graph problems. In her
spare time she likes to read books, learns to play piano and studies French.
Thatchaphol Saranurak is a faculty member of the Electrical Engineering and
Computer Science Department at the University of Michigan. Prior to this, he
spent two years as a research assistant professor at the Toyota Technological
Institute at Chicago. Thatchaphol received his Ph. D. from KTH Royal Institute
of Technology, Stockholm, in 2018 under the supervision of Danupon Nanongkai.
His main research interest is in graph algorithms with a current focus on dynamic,
local, and distributed algorithms. He likes sushi and Japanese manga.
T HEORY OF C OMPUTING, Volume 19 (8), 2023, pp. 1โ71 71