An efficient algorithm for 1D fitting

This algorithm was originally developed for the KGI project for use in GPU memory access protection. It has many, more general, applications. When I derived this, I was not able, through an online search, to find an algorithm that achieved the same results. Maybe this has been developed before, maybe it hasn't, but you are welcome to use my original work if it suits your needs.

Definitions

Let a "1D dashed line segment" be defined as a set of N open interval line segments in a one-dimensional coordinate system, each segment with equal length L and starting points defined by the set of integers:

C + i * S (i=0 .. i=N-1) where:

N, L, C and S are finite integers
N and L are positive.
S > L

For convenience of expression, define a "dash" of a 1D dashed line segment as a single member of the set of open interval line segments in the 1D dashed line segment. Further let the terms "dash length" refer to L and "dash separation" refer to S.

Let the inverse of a 1D dashed line segment be defined to exist for all 1D dashed line segments. The inverse will be represented by a 1D dashed line segment consisting of the inter-segment gaps of the original (excluding open interval endpoints) and an additional segment of the same length starting at the dash end point with the greatest value in the original 1D dashed line segment. That is to say, the set of N open interval line segments with length S - L and starting points defined by the set of integers:

C + L + i * S (i=0 .. i=N-1)

Note: the inverse operation is not reversible and biased arbitrarily towards the positive.

Let one 1D dashed line segment be said to "contain" a second 1D dashed line segment iff the set of all points in all dashes of the second is present in the set of all points in all dashes of the first.

Let one 1D dashed line segment be said to "intersect" a second 1D dashed line segment iff the set of all points in all dashes of the first contains at least one point in the set of all points in all dashes of the second.

Note: this algorithm would also work if "dashes" were defined as half-open intervals, as long as the side of the dash which is open is consistant throughout.

Problem statement

Given two 1D dashed line segments, determine whether the first contains the second.
Given two 1D dashed line segments, determine whether they intersect.

Applications

In order to improve Internet searchability, I now restate the problem in terms relevant to areas of application.

Real-time scheduling: Determine the schedulability of two hard periodic tasks with known fixed start times and known fixed cancellation times.

Memory management: Determine the interleavability if two data arrays with inter-member stride greater than member data length.

I don't know enough of the lingo of the fitting, covering, cutting and packing operational science fields to meaningfully express the problem in those terms, but the algorithm does have application potential in that field.

Supporting Theorems

(This is the pedantic "no duh" section, which you can skip if not interested in mathematical formalities.)

Theorem 1

Given two 1D dashed line segments A and B, defined by the parameters C, L, N, S and C', L', N', S', respectively: A contains B iff the inverse of A does not intersect B and:

C' >= C
C' + L' + (N' - 1) * S' <= C + N * S

Proof

Left to inspection, for now.

Discussion

Thus the two problem statements above are equivalent for cases where the range of points in A meets or exceeds that of B, through inverting A. Assuming multiplication is considered O(1) for the desired application, the range condition test and the inversion operation are both O(1).

Theorem 2a

Given two 1D dashed line segments A and B, defined by the parameters C, L, N, S and C', L', N', S', respectively, and generating a new 1D dashed line segment A' by adding an integer multiple of S, M * S, to C while retaining all other parameters the same, A' contains B iff A contains B, providing the following condition is satisfied:

C + M * S <= C'

Proof

Left to inspection, for now.

Theorem 2b

Given two 1D dashed line segments A and B, defined by the parameters C, L, N, S and C', L', N', S', respectively, and generating a new 1D dashed line segment A' by subtracting an integer, M < N, from N while retaining all other parameters the same, A' contains B iff A contains B, providing the following condition is satisfied:

C' + L' + (N' - 1) * S' <= C + L + (N - M - 1) * S

Proof

Left to inspection, for now.

Discussion

Taken together, Theorems 2a and 2b simply state that extra dashes at the beginning and end of A which are beyond the range of the set of points in the dashes of B can be eliminated without affecting the containment test. Assuming multiplication and division are considered O(1) for the desired application, this operation is O(1).

Theorem 3

Given two 1D dashed line segments A and B, with dash length L, and L', and generating two new 1D dashed line segments A' and B' by subtracting an integer M from L and L' while retaining all other parameters the same: A' contains B' iff A contains B, subject to the following conditions:

M < L
M < L'

Proof

Left to inspection, for now.

Discussion

Reduction of the dash length can be done to express the containment test in equivalent terms. This operation is O(1).

Theorem 4

Given two 1D dashed line segments A and B, with dash separation S, and S', and generating a new 1D dashed line segment B' by subtracting an integer multiple of S, P * S, from S' while retaining all other parameters the same, subject to the constraint that P * S < S': A intersects B' iff A intersects B, and A contains B' iff A contains B.

Proof

Left to inspection, for now.

Discussion

Reduction of the larger dash spacing to a non-zero modulus of the smaller dash spacing can be done to express the above problem statement in equivalent terms. (This can perhaps be best viewed as "aliasing" the dashes in A.) Assuming the modulus operation is considered O(1) for the desired application, this operation is O(1).

Note: If the original operands met the restriction for Theorem 1, this operation maintains the contraints required to use Theorem 1 on the new operands.

Theorem 5

Given two 1D dashed line segments A and B, with starting points C, and C', and generating two new 1D dashed line segments A' and B' by subtracting an integer M from C and C' while retaining all other parameters the same: A' intersects B' iff A intersects B, and A' contains B' iff A contains B.

Proof

Left to inspection, for now.

Discussion

Translation of the coordinate system can be done to express the above problem statement in equivalent terms. This operation is O(1). This theorem is used only in the capacity of computer optimization and is not necessary for a strict application of the algorithm.

Algorithm description

When all was said and done, I looked at the algorithm and found it to be an enhancement of the Euclidean Algorithm, with the same general order of complexity. Using storage of values during recursion steps, useful numerical results can be back-calculated without altering the order of complexity. For presentation purposes, we consider only the boolean form of the problem statement: "Determine whether one 1D dashed line segment contains a second." We will refer to the 1D dashed line segments simply as "operands" for brevity.

The algorithm is recursive and consists of the following steps:

Swap the operands.
Apply Theorems 2a and 2b to remove superfluous dashes from the first operand.
Theorem 5 may be applied to regauge the coordinate system for computational convenience.
Invert the operands.
Apply Theorem 3 to reduce both dash lengths equally such that the dash length of the second operand is 1.
Apply Theorem 4 to "alias" dashes in the first operand. Check for termination as described below.
Apply Theorems 2a and 2b to remove superfluous dashes from the first operand.

Discussion

Steps 1 and 4 represent applications of Theorem 1 and its contrapositive, expressed in an algebraically equivalent manipulation.

If, in step 6, the application of the maximum P permitted by Theorem 4's P * S < S' test cannot generate a new 1D dashed line segment because it would result in a value of S equal to L for B' (thus violating the definition of a 1D dashed line segment,) the algorithm terminates. A trivial test will determine whether the first operand fully contains the other. This test will have the same truth value as the starting operands. This condition is guaranteed to occur.

Calculating the exact order of complexity is something I'll leave to anyone who enjoys such activity, however, it is easily demonstrated that Euclid's algorithm is performed during the process and acts as a limiting case.

Sample Code

Of course, once coded and optimized, the algorithm simplifies to a less intuitive form. In the below sample, a simple recursive rendition, the variable names translate as follows from the conventions used above: C:s1, S:p1, L:w1, N:h1, C':s2, S':p2, L':w2, N':h2. (The variables below are named in graphics memory management style: start, pitch, width, height.)


unsigned int lev;

unsigned int dash_reduce(unsigned int s2, unsigned int p2, 
                         unsigned int w, unsigned int p1) {
        unsigned int dashes;

        lev++;
        if (s2 > w) return 1;
        if (!p2) return 0;
        if (p2 == 1) return (w - s2 + 2);
        if (p1 > p2 + w) return ((w - s2)/p2 + 2);
        dashes = dash_reduce((w - s2) % p2, p1 % p2, p2 + w - p1, p2);
        if (dashes == 0) return 0;
        return (((dashes-1) * p1 + w - s2)/p2 + 2);
}

int optimal_dash(unsigned int s1, unsigned int p1, 
                 unsigned int w1, unsigned int h1, 
                 unsigned int s2, unsigned int p2, 
                 unsigned int w2, unsigned int h2, int *ev) {
        unsigned int w, len;

        /* Handle some trivial cases */
        if (s2 < s1) return -1;
        if (s2 + p2 * h2 + w2 > s1 + p1 * h1 + w1) return -1;
        if (p1 <= w1 + 1) return 0;
        if (w2 > w1) return -1;
        if (p2 < 2) {
          if (s2 + p2 * h2 + w2 <= s1 + w1) return 0;
          return -1;
        }
	s2 -= s1;
	s1 = 0;

        lev = 0;
        len = dash_reduce(s2 - (s2/p1 * p1), p2, w1 - w2, p1);
        *ev = lev;

        if (!len) return 0;
        if (len > h2 + 1) return 0;
        return -1;
}

An "unrolled" version (finite recursion without stack use) of the algorithm for parameters limited to a given unsigned integer type size has also been coded.

Copyright (c) October 2005 Brian S. Julin