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

For convenience of expression, define a "dash" of a

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:

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.*

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

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.

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

**M < L****M < L'**

*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.*

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.

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.

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