Improved Algorithms for Allen's Interval Algebra by Dynamic Programming with Sublinear Partitioning

1 Introduction

Allen's interval algebra (ALLEN) is one of the most wellknown examples of qualitative temporal reasoning where the task is to decide whether a set of (typically incompletely specified) intervals in R2 can be ordered in a consistent way. ALLEN is an influential formalism with a wide range of applications in artificial intelligence, and for a handful of concrete examples we may e.g. mention planning [Allen and Koomen, 1983; Dorn, 1995; Mudrov´a and Hawes, 2015;

∗ Partially supported by the Swedish research council (VR) under grant 2019-03690.

Pelavin and Allen, 1987], natural language processing [Denis and Muller, 2011; Song and Cohen, 1988], and molecular biology [Golumbic and Shamir, 1993]. The second major problem that we consider, the cardinal direction point algebra (CDPA), can be seen as an offshoot of Allen's interval algebra where the task is to reason about directions of objects in a 2-dimensional space. This algebra has seen applications in e.g. geographical information science and image retrieval and we refer the reader to the survey by Dylla et al. [2017] for additional references and applications for both these formalisms.

Both these formalisms are in general NP-hard and admit non-trivial tractable fragments. Hence, in actual applications one is rarely contempt with reasoning only with tractable fragments, which spurs the question of how fast we can solve NP-hard qualitative reasoning tasks. First, we need to carefully establish a baseline upper bound that we can use to measure whether an algorithm for these problems is indeed an improvement or not. This is easy for many types of problems over finite universes, e.g., finite domain constraint satisfaction problems (CSPs) and the Boolean satisfiability problem, which can always be solved simply by enumerating all possible assignments from variables to the finite universe. Clearly, this cannot be done for ALLEN or CDPA, but these problems can be solved in 2O(n·log n) time by enumerating certain total orderings, which for ALLEN gives the precise upper bound O∗ ((2n)2n ) [Jonsson and Lagerkvist, 2017] 1 . Hence, the question is whether this upper bound can be improved, and we stress that this is sometimes known to be possible (e.g., k-SAT and k-COLORING) but that there also exist problems where this is conjectured to be impossible (e.g., CNFSAT, SAT with unrestricted clause length). However, this has been proven possible for ALLEN which was recently solved in O∗ ((1.0615n)n ) time [Eriksson and Lagerkvist, 2021] by a novel dynamic programming algorithm. Additionally, if ALLEN is restricted to intervals of length one, then it can even be solved in 2O(n log logn) time [Dabrowski et al., 2020]. A faster O∗ (cn ) time algorithm is also known for the special case where no point occurs inside more than k intervals [Eriksson and Lagerkvist, 2022]. However, despite these improvements, we are still far away from an unconditional single-exponential O∗ (cn ) time algorithm and even further away from the bestknown lower bounds which only rule out subexponential algorithms running in 2o(n) time under the exponential-time hypothesis [Jonsson et al., 2021].

1 The notation O∗ (·) suppresses polynomial factors and n denotes the number of intervals.

In this paper we make a significant push for ALLEN and CDPA by introducing a new variant of dynamic programming; dynamic programming with sublinear partitioning, which is exceptionally suited for problems related to orderings. After having introduced the necessary preliminaries (in Section 2) we first showcase our new method for ALLEN in Section 3 where we obtain the bound O∗ (( cn logn )n ), for some constant c ≥ 1. This is a major improvement compared to the aforementioned bound of O∗ ((1.0615n)n ) and thus proves that ALLEN is solvable in O∗ (f(n)n ) time for f ∈ o(n), i.e., a significant leap towards a O∗ (cn ) time algorithm. To exemplify that our method is not limited to ALLEN we continue (in Section 4) by showing how it can be tailored to solve CDPA faster than the general case of ALLEN. Here, we obtain the bound O∗ (( cn log n )2n/3 ) for a constant c, which is much faster than the algorithm for ALLEN. The main idea behind our dynamic programming strategy is to use a table consisting of records, representing (partially) placed start- and end-points of intervals, where the twist is that the size of a record is not fixed beforehand but may expand up to a certain size during the execution of the algorithm. To achieve this we use a similar idea to the one presented in Eriksson & Lagerkvist [2021] but we analyze the structure of potential solutions much deeper. We manage to identify redundant information by using the fact that if we know the relative position of more variables then we need to keep track of fewer potential positions. While previous approaches have required keeping track of, or storing information corresponding to, a linear number of partitions measured in the number of variables, we here manage to solve the task while only partitioning the variables into a sublinear number of partitions. Consequently, the upper limit of information stored in a record is bounded tighter by the number of variables than any earlier approach. In turn, this leads to a lower number of maximum records, and hence a lower overall complexity. This idea of managing with only a sublinear number of partitioning will be our main result throughout the paper. However, achieving this is as expected far from trivial.

Last, it is worth observing that virtually all qualitative tem-

poral and spatial reasoning problems can be formulated as CSPs over a template containing a strict partial order or an acyclic relation [Jonsson et al., 2021]. Hence, all members of this diverse and rich class of problems are intrinsically related to the existence of certain orders, and it is not a large stretch of the imagination to conjecture that more problems can be solved with our approach. Most pressingly: Can dynamic programming with sublinear partitioning be used to solve an NP-hard qualitative reasoning problem in O∗ (cn ) time? We discuss this and additional questions in Section 5.

The proofs of statements marked with an asterisk (*) have been omitted due to space constraints.

2 Preliminaries

Given a set of finitary relations Γ defined on a (potentially infinite) set D of values, we define the constraint satisfaction problem over Γ (CSP(Γ)) as follows.

CSP(Γ)

Instance: A tuple (V,C), where V is a set of variables and C a set of constraints of the form R(v1, . . . , vt), where t is the arity of R ∈ Γ and v1, . . . , vt ∈ V .

Question: Is there a function f : V → D such that (f(v1), . . . , f(vt)) ∈ R for every R(v1, . . . , vt) ∈ C?

The set Γ is referred to as a constraint language, while the function f is a function satisfying the instance I, or simply a model of I. Given an instance I of CSP(Γ), we let ||I|| denote the number of bits required to represent I.

We continue by defining total orders and order relations induced by a given total order. A total order (S,≤) is a relation ≤ on set S which is reflexive (for all x ∈ S, x ≤ x), antisymmetric (for all x, y ∈ S, if x ≤ y and y ≤ x, then x = y), transitive (if x ≤ y and y ≤ z, then x ≤ z), and strongly connected (for all x, y ∈ S, either x ≤ y or y ≤ x). If ⊙ ∈ {<, >, =} and T = (S, ≤T ) is a total order then we write ⊙T for the relation induced by T: x <T y if x ≤T y and y ≤T x does not hold, conversely for >T , and x =T y if x ≤T y and y ≤T x. The total number of different total orders for a variable set of n elements is known as n'th Ordered Bell Number (OBN(n)) and is in O∗ (( n e log 2 )n ) and O∗ ((0.5307n)n ) (recall that the O∗ (·) notation supresses polynomial factors).

2.1 Allen's Interval Algebra

In Allen's interval algebra the basic relations consists of 13 relations between intervals over R2 (summarized in Table 1). The computational problem is then defined as follows.

ALLEN'S INTERVAL ALGEBRA

Instance: A set of intervals V and a set of binary constraints C of the form c(X, Y ) where c ⊆ {<, >, =, m, mi, o, oi, s, si, d, di, f, f i} and X, Y ∈ V .

Question: Is there a total order T = (S,≤) and a function f : V → S2 such that for all X ∈ V with f(X) = (u, v) then u < v and for every constraint c(X, Y ) ∈ C then f(X) ⊙ f(Y ) for some ⊙ ∈ c?

Equivalently, the problem can be defined as CSP(A) where A contains the 13 basic relations in Table 1 and is closed under union. Note from Table 1 that any relation between two intervals can be described using point relations (<, > and =) between the start- and end-point of the two intervals. For a set of intervals V we write V - for the set of start-points and V + for the set of end-points.

2.2 Cardinal Direction Point Algebra

We follow the projection based approach of Frank [1991] and define the second major problem of the paper as follows.

CARDINAL DIRECTION POINT ALGEBRA

Instance: A set of pairs of points, V , and a set of binary constraints C, of the form c(u, v), where c ⊆ {{<, >, =} × {{<, >, =}} and u, v ∈ V .

Question: Is there a function f : V → {1, . . . , |V |}2 such that for every constraint c(u, v) ∈ C then f(u) = (ux, uy), f(v) = (vx, vy), ux⊙xvx and uy⊙yvy with (⊙x, ⊙y) ∈ c?

Alternatively, the problem can be seen as whether V can be ordered into two separate total orderings such that one represents the x-dimension and the other the y, such that they combined satisfy all constraints. Another alternative is viewing CDPA as a sub-problem of ALLEN (e.g. by letting a- represent ax and a+ represent the ay coordinate of a point a).

3 ANewAlgorithm for Allen's Interval Algebra

In this section we present a novel, improved algorithm for ALLEN based on dynamic programming. The twist with this algorithm is that the dimension of our table, or the size of the records stored, is not static, but may dynamically change during the execution of the algorithm. This dynamic programming is realized by using records functioning as elements or keys in a map that is dynamically built, and we refer to this programming scheme as dynamic programming with sublinear partitioning. Here, sublinear refers to the fact that we partition the variable set into a sublinear number of partitions. Each such record represents a set of S variables that have been used to construct this record, and then pairs of disjoint subsets of S, and Booleans. The subsets of S are here used to keep track of the (relevant) ordering between variables that have been used, while the Booleans serve as markers that tell us if a certain subset has ever been merged with another subset or not. This is useful, since if they have previously been merged with some other subset, we do not want to add any new variables to this subset, since we could then get inconsistent cases where x = y, y = z but x < z. Combined, these partitions of S represent an ordered partition, but we will not strictly use them as such.

We also introduce two notations for records: left-heaviness where we require start-points of intervals in a record to always be in either of the first two subsets, and pair-placing where we require whole intervals, and not just a start- or an end-point, to be placed at the same time into a record. Formally, these notions are now defined as follows.

Definition 1. For a CSP(A) instance (V,C) we say that r = (S, (S1,B1), . . . , (Sm,Bm)) is a Record if the following holds:

1. S ⊆ V - ∪ V +,
2. B1, . . . ,Bm ∈ {0, 1}, and
3. S1, . . . , Sm is a partitioning of S.

We say that m is the size of the record. A record is left-heavy if Si ∩ V - = ∅ for all 3 ≤ i ≤ m. A record is pair-placing if and only if for all x- ∈ Si for any i, there is a j > i such that x+ ∈ Sj or i = j and Bi = 0.

For any two variables u, v in some Record with u ∈ Si and v ∈ Sj, then we also assume that u < v if i < j, u > v if i > j and that u = v if i = j and Bi = 1. However, if i = j and Bi = 0 we have to assume all three relations between u and v holds. Further, a Record contradicts C if and only if there is a constraint c(X, Y ) ∈ C such that no assumption we can make about the relations X and Y given said Record will satisfy c(X, Y ).

Generalization between records, i.e. whether a record A can be converted to a record B by adding variables and merging subsets, will be important, and we define the following concept.

Definition 2. We say that for two records

then r2 is a generalization of r1 if:

1. S1 ⊆ S2,
2. k ≤m (r2 is not larger than r1),
3. for every S1,i there is a S2,j such that S1,i ⊆ S2,j (no set in r1 is split in r2),
4. for every j then B2,j = 1 if and only if either S2,j = ∅ or if there is an i such that B1,i = 1 and S1,i = S2,j, otherwise B2,j = 0 (only empty or unchanged sets keep their positive B value), and
5. for all variables x ∈ S1,i and x′ ∈ S1,i′ with i ≤ i′ then x ∈ S2,j and x′ ∈ S2,j ′ such that j ≤ j ′ (ordering is kept).

For a record r = (S, (S1,B1), . . . , (Sm,Bm)) we can recursively generate all generalizations r′ = (S, (S′1 ,B′1 ), . . . , (S′m′ ,B′m′)) with m′ ≤ m in O∗ (3m) time. We do this by branching on every Si and constructing two new records, one where Si is merged with Si-1 (when these exists) and (Si-1,Bi-1) is removed and one where we also replace (Si-1, Bi-1) with (∅, 1). For the value of B′i we strictly follow the definition. By checking if a given result has earlier already been created we can also prevent calling the recursion with the same record more than once. Our complexity of O∗ (3m) then comes from that either (S′ i , B′i ) = (Si, Bi), (S′ i-1 , B′i-1 ) = (Si-1, Bi-1) ∪ (Si, Bi) or (S′ i , B′i ) = (Si-1, Bi-1) ∪ (Si, Bi) and (S′ i-1 ,B′i-1 ) = (∅, 1), creating fewer than 3m different possibilities. Let GenerateGeneralizations(r,H) be the function doing this for a record r and where H is the set of all previously generated records. Note that the records in H does not need to be generalizations of r, since this set is just used to prevent unessesary computational complexity.

After this we want to continue by adding new intervals to existing records. When adding new intervals to records we do so in such a manner that given an ALLEN instance I = (V, C) we never contradict C, while, if given a left-heavy and pairplacing record, the result is also left-heavy and pair-placing.

We briefly remind the reader that for an interval X the points x- and x+ represents the start- and endpoint of said interval.

1: function ADD(I = (V,C), R = (S, (S1, B1), . . . , (Sm, Bm)), Output) 2: for every x-, x+ ∈ (V - ∪ V +) \ ⋃mi=1 Si and every 2 ≤ j ≤ m with Bj = 1 do 3: if for all X′ ∈ V with x′- ∈ Su and x′+ ∈ Sv all c(X, X′ ), c(X′ , X) ∈ C are satisfied by x- = 2, x+ = j, x′- = u and x′+ = v then 4: Output ←GenerateGeneralizations(( S∪{x-, x+}, (S1, B1), (S2∪{x-}, 1), . . . , (Sj ∪ {x+}, 1), . . . , (Sm, Bm)), Output) 5: end if 6: end for 7: return Output 8: end function

As we can see, Algorithm 1 guarantees that for any pair X we add to a record (S, (S1,B1), . . . , (Sm,Bm)), all constraints c(X,X′ ) ∈ C with X′ ∈ S are satisfied. Quite obviously the work done in Algorithm 1 (excluding the work done in GenerateGeneralizations) is also polynomial in terms of ||I|| +m. By only ever adding x- to S2 the algorithm keeps left-heaviness if the input is left-heavy, and as we add one pair (x-, x+) at a time, the result is also pair-placing if the input is pair-placing. Here we also see how the Boolean variables Bi are used, as we only add new start- and end-points to sets with a Boolean set to 1. Combined with the definition of generalization this helps ensure we avoid situations where now x = y and x = z, but x < z in an earlier record which the current record is a generalization of.

With Algorithm 1 we now have everything we need for solving ALLEN. However, we want to optimize our method and hence want to limit our records to a certain size, i.e. limit our m. The choice of m needs to be big enough to ensure correctness of the algorithm, i.e. big enough so that we can always ensure that every pair can be placed into some record, while the number of already placed pairs increases. Choosing m = 4n would trivially give us enough room to place every single variable, be it a start- or end-point, in any possible ordering. To do better we first make the following observation: given an arbitrary ordering of V - ∪ V + and placing pairs following the ordering of the start-points, if we let k be the number of pairs yet to be placed, we need at most 2k pairs (Si,Bi) for which Bi = 1. This leads to a situation where we have records where for every second pair, the Boolean is set to one while for the other pairs it is set to zero, while still allowing the placement of every remaining variable. If more than 2k + 1 pairs with Bi = 0 exists, there must exist two pairs (Sj, 0) and (Sj+1, 0) and hence a generalization with (Sj ∪ Sj+1, 0), but which is otherwise identical. Hence we take m = 4k + 1, which also leads us to our main algorithm as presented in Algorithm 2.

Algorithm 2 Solving ALLEN by dynamic programming.

1: function MAIN(I = (V,C)) 2: R← {(∅, (S1 = ∅, 1), . . . , (S4n+3 = ∅, 1))} 3: for every record r = (S, (S1, B1), . . . , (Sm, Bm)) ∈ R do 4: if |S| = 2n then 5: return True 6: else if m ≤ 4(n - | ⋃mi=1 Si|) + 3 then 7: R ←Add(I , r, R) 8: end if 9: end for 10: return False 11: end function

In Algorithm 2 we see how we make use of this decreasing number of pairs (S,B) by ignoring any records containing more pairs that we think we will need. This algorithm works by iteratively calling Algorithm 1 with new records, until every record has been either tested, or we find a record containing all intervals (in which case we must have a satisfiable instance).

Lemma 3. For an arbitrary CSP(A) instance I, Algorithm 2 returns True if and only if I is a satisfiable instance.

Proof. We begin by proving completeness. Given a satisfiable instance I = (V,C), we know there exists a function f : V - ∪ V + → N such that f satisfies every constraint in C. Let V - = {x-1 , . . . , x-n } and V + = {x+1 , . . . , x+n } such that f(x-1 ) ≤ f(x-2 ) ≤ · · · ≤ f(x-n ), i.e., each pair x-i , x+i is assigned an index i according to some ordering of the start-points of the intervals. Define the sets T1, . . . , Tn such that x±j ∈ Ti if and only if there is no variable v ∈ {x-i , x+i , . . . , x-n , x+n } such that f(v) < f(x±j ). Furthermore, define the auxiliary function #< : V - ∪ V + ×2V -∪V + →N such that #<(x±j ,U) returns the number of variables y such that f(y) < f(x±j ) and y ∈ U. From this we define the functions f#,i : V - ∪ V + → {1, . . . , 4n+1}:

Since f#,i follows the same ordering as f, it is also a solution for I[{x-i , x+i , . . . , x-n , x+n }], i.e. the sub-problem of I where only variables {x-i , x+i , . . . , x-n , x+n } are considered. Additionally, for all intervals Y ∈ V and Xi ∈ {Ti ∪ . . . ∪ Tn}, f#,i also satisfies any constraints c(Xi, Y ) ∈ C. For each i ∈ {0, . . . , n} define the record

such that x±j ∈ Si′ ,i if and only if f#,i(x±j , ) = i′ and j ≤ i, and Bi′ ,i = 1 if and only if Si′ ,i ∩ Si = ∅ and Bi′ ,i = 0 otherwise. According to our definitions ri+1 is a generalization of ri, and every record is both left-heavy and pair-placing. As such, Algorithm 2 generates all records ri, i ∈ {0, . . . , n} starting from the original record constructed at line 2, which is equivalent to r0. By doing so the algorithm must reach a record containing all variables (rn), and hence returns True.

For soundness, assume that the algorithm returns True. Then there must be an ordering of the variables in V , X1, . . . ,Xn, and sequence of records r0, . . . , rn such that

for all i ∈ {0, . . . , n} and such that

is a generalization of ri for all j ∈ {i + 1, . . . , n} when

This holds because of how GenerateGeneralizations together with Add constructs records. Since Bi,j must be 1 for Add to add new a new pair to Si,j, since (1) Bi,j is set to 0 as soon as two sets are merged into Si,j, and (2) every constraint c(Xi,Xi′) ∈ C must be satisfied for all i′ < i, for Xi to be added. Given this set, define the function h : V - ∪ V + → {1, . . . , 4n + 3} such that (assuming i > i′ ) if x±i ∈ Sj,i and x±i′ ∈ Sj ′ ,i with j ⊙ j ′ then h(x±i ) ⊙h(x±i′ ). Since every c(Xi, Xj) ∈ C is satisfied for all j < i when Xi is added (since h orders Xi according to its position when added), and since this is true for all i, h must satisfy C. Hence, h is a solution for I, implying that our algorithm is sound. With both soundness and completeness proven, the algorithm must also be correct, and hence we are done.

With all supporting lemmas in place, we can now present the main result of the section.

Theorem 4. There is a constant c such that ALLEN can be solved in O∗ (( cn ln n )n ) time and space using dynamic programming with sublinear partitioning.

Proof. We know that Algorithm 2 is correct from Lemma 3. For the run-time we note that Add is polynomial (with respect to n and m), GenerateGeneralizations adds fewer than 3m sets to Output and does linear work in terms of the size of the return. Our Main itself also only does polynomial work for each record, and hence the question that remains is the maximal possible number of records. With the way we limit records size, we have that for a certain m there are at most poly(n, m, ) · 24(n-m) ( nm)(8(n - m))m different records with m pairs placed. Here, 24(n-m) is an overestimation for our possible assignments of Booleans, ( nm) is the different ways to choose pairs, 2m is from start-points being in either S1,m or S2,m, and (4(n-m))m comes from the number of ways to place end-points into the available Si,m. In total we hence have roughly ∑n0=m 24(n-m) ( nm)(8(n-m))m records, which is linear in terms of the maximum value of 24(n-m) ( nm)(8(n - m))m. Since 24(n-m) ( nm)8m ≤ 32n we are left with having to maximize (n - m)m. Since n,m, n - m ≥ 0 and n,m ∈ N, replacing n-m with x (and m with n - x) and derivation gives us d dx xn-x = xn-x-1 (n-x-x lnx). The maximum must then occur when n = x + x lnx, which have no exact finite expression, but can be estimated as x = n ln n ln n . Since n < n ln n ln n ln n ln n ln n this gives us an overestimation of x, and hence we get a valid upper bound on xn-x by also approximating n - x = n. Inserting this in the original formula and assuming n is large enough gives us

Hence, we have an upper bound on the form O∗ (( cn ln n )n ) where c is some constant, which completes the proof.

Compared to the previous best known upper bound of O∗ ((1.0615n)n ) [Eriksson and Lagerkvist, 2021] this is a clear improvement. In fact, we even changed the category ALLEN belongs to by pushing it below O∗ ((cn)n ) for every constant c > 0. This may be a major cornerstone towards a single-exponential algorithm for ALLEN.

While the algorithm presented here only decides consitency by outputing a True or False answer, one can using standard implementations of e.g. backpoints also use the algorithm to yield solutions to satisfiable instances. Or even modify the algorithm to instead count solutions.

4 Cardinal Direction Calculus

In this section we focus on CDPA. While CDPA can be reduced to a subproblem of ALLEN, the problem is interesting in its own right and is typically viewed as an independent formalism. The CDPA formalism also allows significantly better complexity than the general case of ALLEN and we will show that CDC can be solved in O∗ (( cn logn )2n/3 ) time for a constant c.

We achieve this in three steps: first we modify the algorithm from Eriksson & Lagerkvist [2021] to work in the now two-dimensional space. Second, we show that by running the modified version four times in different combinations of directions, while not storing orderings longer than roughly n/3, the worst case is significantly improved. Last, we show how the method from Section 3 can be applied, yielding the final complexity of O∗ (( cn log n )2n/3 ).

Briefly, the algorithm presented in Eriksson & Lagerkvist [2021] works on intervals by dynamic programming and adding points in a brute force way (regardless of whether they are start-points or end-points) in sets of equality, one set of a time, to the end of the working ordering. While the complexity of this approach is generally bounded by the size of the ordering, we can further bound the size of said ordering, since if we remove whole intervals from the ordering when both start- and end-point are placed, the ordering will never contain any end-points, except in the very last position.

For our first approach to CDPA we follow a similar strategy but in two dimensions: we use dynamic programming and keep track of two active orderings, one in the direction of positive x-relations, and one positive y-relations direction. We also keep track of points already having been placed into both orderings, and as a result we also, directly or indirectly, know which variables that have not been used in either ordering. Effectively, we have records (S, (Sx,≤x), (Sy,≤y)) where (Sx ∪ Sy) ⊆ S ⊆ V while Sx ∩ Sy = ∅ and both (Sx, ≤x) and (Sx, ≤x) are total orders. By only placing (sets) of points into the smaller of the two orderings, and only at the very end, and then "forgetting" points used in both orderings, we achieve the worst case for this approach. Again, these partitions of S form an ordered partition, but we will not strictly use them as such.

Lemma 5. (*) CDPA can be solved in O∗ (23n/2OBN(n/2)2 ) or O∗ ((0.7506n)n ) time with dynamic programming.

This is already enough to surpass the previous best result for ALLEN [Eriksson and Lagerkvist, 2021] but does not beat the bound from Section 3. To improve this approach for CDPA consider the scenario of having the solution be all points on a diagonal line from positve X and negative Y towards negative X and positive Y . This represents the worst-case for the algorithm outlined previously and naturally raises the question of whether one could order in negative x- or y-direction instead (since this would yield O∗ (1) complexity for this case instead). However, there are of course other cases (we could just mirror this example along either axis) that are instead the worst case for this approach. So, instead we try all four possible combinations of directions: positive x + positive y, positive x + negative y, negative x + positive y and negative x + negative y. Using this approach and not allowing the orderings to grow larger than some maximum, we are able to avoid all these worst cases.

Definition 6. Given a finite total ordering (S, <) and an integer k ≥ 0 let Subk((S,<)) be the first k elements in (S,<), or S if k ≥ |S|.

Lemma 7. For any distribution of a finite set of two dimensional points V in two dimensional space, there are two total orders Tx = (V,≤x) and Ty = (V,≤y) such that for all u, v ∈ V if ux ⊙ vx then u ⊙x v and if uy ⊙ vy then u ⊙y v and such that |Subk(Tx) ∩ Subk(Ty)| ≥ k - 1/3n for every 0 ≤ k ≤ n.

Proof. Constructing orderings such that such that for all u, v ∈ V if ux ⊙ vx then u ⊙x v and if uy ⊙ vy then u ⊙y v is trivial. From here on, we assume that n is a multiple of 3. Take the four total orders that can be generated by sorting our distribution in (1) either positive or negative and (2) either x- or y-direction. Call these four total orders T + x = (V,≤+x ), T - x = (V,≤-x ), T + y = (V,≤+y ) and T - y = (V,≤-y ). Let k++ > n/3 be the smallest integer such that |Subk++ (T + x ) \ Subk++ (T + y )| = n/3 but

y

x

Figure 1: Graphic representation of the nine sets described by V , Subk++ (T + x ), Subk++ (T + y ), Subk-- (T - x ) and Subk-- (T - y ). E.g. x1,1 = |Subk++ (T + x ) ∩Subk++ (T + y )|, x1,2 = |Subk++ (T + y ) \ Subk++ (T + x ) ∪Subk-- (T - x )|, x1,3 = |Subk++ (T + y ) ∩Subk-- (T - x )| and x2,1 = |Subk++ (T + x ) \ Subk++ (T + y ) ∪Subk-- (T - y )|.

|Subk+++1(T + x ) \ Subk+++1(T + y )| > n/3, or if no such integer exists, then k++ = n. Similarly we define k-- for T - x and T - y , k+- for T - x and T + y and k-+ for T + x and T - y . By symmetry and renaming we can safely assume that k++ is not smaller than any of k+-, k-+ and k--. Using Subk++ (T + x ), Subk-- (T - x ), Subk++ (T + y ) and Subk-- (T - y ) we now partition V into nine subsets and label these as shown in Figure 1. We will now prove that k++ = n using proof by contradiction. First we assume that k++ < n but that k++ + k-- ≥ n:

In this case we know that n-k++ ≤ k--, hence |Subn-k++ (T - x ) \ Subn-k++ (T - y )| ≤ n/3 and that |Subn-k++-1(T - x ) \ Subn-k++-1(T - y )| ≤ n/3. But Subk++ (T + x ) \ Subk++ (T + y ) = Subn-k++ (T - y ) \ Subn-k++ (T - x ) and Subk+++1(T + x ) \ Subk+++1(T + y ) = Subn-k++-1(T - y ) \ Subn-k++-1(T - x ). This leads to a contradiction since

Hence, our assumption must be incorrect.

In our second case we assume that k++ < n but that k++ + k-- < n: Our first observation is that x1,2 +x1,3 = x2,3 +x1,3 = n/3 by our definition of k++. For simplicity we will assume x1,2 = x2,3 and similarly x2,1 = x3,2. Again, by arguments about symmetry we can safely assume that x1,3 ≥ x3,1. We have that x1,3 ≥ n/6, otherwise x1,2 + x1,3 + x2,3 + x2,1 + x3,1 + x3,2 > n. By our definition of K++, x1,1 < n/3 must hold, otherwise Subk++ (T + x ) ∪ Subk++ (T + y ) = V and k++ = n. Similarly x1,1 ≥ 1, otherwise x1,2 = x2,1 = x3,2 = x2,3 = n/3, which can only be true if n = 0 and then k++ = n. Assume that x3,1 = x1,3 = n/3. This implies that x1,1 + x2,2 + x3,3 = n/3 and x1,2 = x2,1 = 0 and a situation where k+- > k++, as for all n/3 ≤ k ≤ n then k - |Subk(T + x ) ∩Subk(T - y )| ≤ n/3. Hence this also contradicts our original assumption of k++ ≥ k+-. So x3,1 < n/3 and x2,1 > 1 as x2,1 + x3,1 = n/3. But this means that x1,1 + x1,2 + x1,3 + x2,3 + x3,3 < n/3 (recall that all xi,i are disjoint) which in turn implies that Subk++ (T - x ) \ Subk++ (T + y ) < n/3 and hence k++ < k+-. But k++ ≥ k+- so we again have a contradiction! Hence k++ = n is the only viable alternative, completing our proof.

By Lemma 7 the following result becomes fairly straightforward.

Lemma 8. (*) CDPA can be solved in O∗ ((cn)2n/3 ) time with dynamic programming.

To improve this approach further we implement the same methods as we used in Section 3: instead of strictly using orderings we use records containing pairs (Si,Bi) where Si are subsets of V and Bi is the Boolean keeping track of if we can add new variables to the given set or not. Similarly to the ALLEN case we also limit the number of such pairs we allow at once. What differs from ALLEN to CDPA is that we, again, for CDPA need to keep track of two orderings, giving us both (Sx 0 , Bx 0 ), . . . , (Sxm,Bxm) and (Sy 0 , By 0 ), . . . , (Sym, Bym). Hence the final form of the records are (S, (Sx 0 , Bx 0 ), . . . , (Sxm, Bxm), (Sy 0 , By 0 ), . . . , (Sym, Bym)). Further, the notation of left-heaviness needs to be adapted to the use of two ordered partitions: For all i ∈ {0, . . . ,m} every variable in some Sx i also needs to be in either Sy 0 or S2 1 and every variable in Sy i also needs to be in either Sx 0 or Sx 1 . By also balancing Sx 0 ∪Sy 1 and Sy 0 ∪Sy 1 to remain of roughly similar size, we also keep the advantages from our earlier improvements to CDPA. Pair-placing here means that once we place a variable in Sx 1 or Sy 1 we also simultaneously place it in Sy i or Sx i respectively. With this approach, combined with similar logic to our second improvement for CDPA, we at most need as many holes as the current number of unplaced variables. If more is needed, the solution is easier to find in another orientation.

Theorem 9. CDPA can be solved in O∗ (( cn logn )2n/3 ) time using dynamic programming with sublinear partitioning.

Proof. (Sketch) By using records of the form (S, (Sx 0 , Bx 0 ), . . . , (Sx i ,Bx i ), (Sy 0 , By 0 ), . . . , (Sy j ,By j )), balancing Sx 0 ∪ Sy 1 and Sy 0 ∪ Sy 1 to roughly equal size, and using our substitute for left-heaviness and pair-placing, we can apply Algorithm 2 with only a few minor modifications. While we in Lemma 8 effectively found the optimum for |Subk++ (T + x ) \ Subk++ (T + y )|! we are here instead interested in optimizing (2 · |V \ {Subk++ (T + x ) ∪ Subk++ (T + y )}| + 1)|Subk++ (T + x )\Subk++ (T + y )| . I.e., assuming there are m unplaced variables we need at most m holes in both the x and y direction, while partitioning our current variables into the roughly 2m+ 1 possible sets in each direction, yielding (2m+ 1)(1-1/3)n-m. Since this function, for large n, has a smaller optimum than n!, our complexity is directly given by Lemma 8 combined with the same logic as for Theorem 4. Similarly, correctness also follows via similar arguments to those in Theorem 4.

With Theorem 9 in place we now have a o(n)2n/3 algorithm for CDPA.

5 Discussion and Conclusion

While the results presented in the paper yield significant improvement to the worst-case complexity of ALLEN and CDPA, a plethora of questions and open ends remain.

For ALLEN we consider two major open questions left by our results; the first one being the true value of c and the second that our approach with using left-heaviness seems overly restrictive. Is there a better algorithm that does not necessitate the restriction of left-heaviness and instead allows merging sets to both the left and the right? While removing the restriction of left-heaviness is not difficult, it significantly complicates the analysis, and we did therefore not attempt it.

The questions raised for ALLEN naturally also hold for CDPA. However, in this case the value of the exponent is arguably of more interest. While we saw in Section 4 how the exponent 2n/3 occurred naturally, many general problems solvable in 2O(n) time often have 2O(√n) algorithms for the two-dimensional variants. Could this imply that there might be an O∗ ((cn)n/2 ) algorithm for CDPA? Finding such an algorithm, and maybe even improving it further to O∗ (( cn log n )n/2 ) would be very interesting.

The main idea behind the dynamic programming with sublinear partitioning scheme is that we can dynamically restrict the amount of information stored. To the best of our knowledge, this approach has not been explored before in the literature, and we believe that it can be expanded further. For example, while we here focus on only one type of structure, there is nothing preventing us from storing multiple, e.g. exponentially many, different types of structures simultaneously. This concept would likely be enough to at least match the 2O(n log logn) results for ALLEN restricted to only interval length one of [Dabrowski et al., 2020], while keeping the O∗ (( cn lnn )n ) complexity for general ALLEN.

In conclusion, we have in this paper seen how we can use structural properties required by solutions for ALLEN and CDPA instances to achieve, significantly, improved upper bounds for these problems. In particular we have seen how we using dynamic programming combined with optimizing how much information we store in each iteration, can solve ALLEN in O∗ (( cn lnn )n ) time CDPA in O∗ (( cn lnn )2n/3 ) time.

Acknowledgements

We thank the anonymous reviewers for several insightful comments. The first author is partially supported by the National Graduate School in Computer Science (CUGS), Sweden. The second author is partially supported by the Swedish Research Council (VR) under grant 2019-03690.