The Problem Solving/Last Episode

Detecting Oriented Box Intersection
To celebrate the fact that the term is over and that I now have roughly a month to work uninterrupted on my own project, I've decided to work on a problem that is somewhat related - finding an algorithm to detect whether or not two 3D oriented boxes are intersecting each other

Given Information
The algorithm is given as input two oriented boxes defined as:
A:
    position; a
    edge-vectors; q, r, s
B:
    position, b
    edge-vectors: t, u, v

Where:
  - q, r, s are perpendicular to each other and t, u, v are perpendicular to each other.
  - a + q + r + s is the corner of A opposite to a and b + t + u + v is the corner of B opposite to b.

The Unkown
What is an efficient way to tell if two such boxes, A and B intersect?

The Plan
By definition, it is known that two sets intersect if they both contain at least one common element (or point in this case).

Linear separability, which is the ability to separate two sets of points with a linear object like a line or plane, will prove useful here.

With these types of geometrical problems, its always best to try and see if there is a 1 or 2 dimensional equivalent. If an algorithm can be found for those, then it may possible to generalize the solution and come up with the required 3-dimensional solution.

The Attempt
One Dimension
This problem degenerates to that of determining whether or not two line segments intersect. As a consequence of the definition of intersection, its obvious that two line segments intersect if an endpoint of one is within the bounds of the other. Visually, if they do not intersect, then there will be a gap between them.

Therefore, boxes A and B intersect <=> (b <= a <= b + t OR b <= a + q <= b + t OR a <= b <= a + q OR a <= b + t <= a + q).

Two Dimensions
In two dimensions, this becomes more complicated. With an axis aligned box, its obvious that two boxes intersect <=> there is a 1-dimensional intersection on both the x and y axes. The boolean formula would be:

(bx <= ax <= bx + t OR bx <= ax + q <= bx + t OR ax <= bx <= ax + q OR ax <= bx + t <= ax + q) AND
(by <= ay <= by + u OR by <= ay + r <= by + u OR ay <= by <= ay + r OR ay <= by + u <= ay + r)

The above expression is illustrated in the following diagram; while A and B intersect on the x-axis, they do not intersect on the y-axis.

Extending this to the case where the sides of individual boxes are still perpendicular, but where the two boxes are not necessarily aligned to the same axes makes this a bit more tricky. After experimenting with many different pairs of As and Bs, with the intuition that perhaps a version of the axis-aligned approach, modified to use the rotated axes, can be used here; I came up with the following hypothesis:

Two oriented boxes A and B do not intersect iff the projections of A and B on some axis do not intersect.

I know how to prove that this is true in one direction - that two oriented boxes A and B do not intersect if the projections of A and B on some axis do not intersect. Unfortunately, I'm not sure how to formally prove this in the other direction, though I speculate I would need to use the fact that A and B are convex shapes and a theorem relating convex shapes to linear separability.
Proof
Assume A and B are oriented boxes and that the projections of A and B do not intersect on some axis.
Then A and B are linearly separable (i.e., there is some line or plane that separates A and B, perpendicular to that axis).
Then since A and B are linearly separable, A and B do not intersect.

In all tests where A and B did not intersect, it was noted that there was no intersection on at least one of the axes of q, r, t or u. Thus:

Two oriented boxes A and B do not intersect iff the projections of A and B do not intersect on q, r, t or u.

While I haven't been able to produce a proof of this hypothesis, I'll attempt to justify it by saying that the axis-aligned expression is just a special case of this in which the axes of q and t are the same and where the axes of r and u are the same

Thus, I've come up with an algorithm for determining if two boxes in 2D intersect: see if the projections of the boxes onto the axes of q, r, t and u all intersect using the 1D intersection test. If on one of those axes, the boxes are found to be disjoint, then the boxes must be disjoint.

In the following case, A and B do not intersect because their projections are disjoint on an axis of B.

Extending to 3D
I found that extending my 2D algorithm to 3 dimensions, by adding in 1-dimensional intersect tests for the axes defined by s and v, worked on all test cases I tried. Moreover, I devised an alternative way of formulating the 3D algorithm based on the 2D algorithm. Consider the following hypothesis, which is another logical way of extending the 2D algorithm to 3 dimensions:

Two oriented boxes A and B do not intersect iff the projections of A and B onto some plane (particularly, some plane coplanar to a face of A or B) do not intersect.

Observe how the faces of A and B are defined; for example, one face on A has the edge vectors q and r. Thus, in order to test the intersection on that face, the 1D intersection test is performed for q and r. Therefore, with all the faces of A and B, this involves performing the same algorithm as above.

More formally, the algorithm is:
1. For each vector, w, in {q, r, s, t, u, v}:
    1a) Project the corners of A and B onto w.
    1b) Since the projections are all 1-dimensional values, determine the largest value for the projection of A and the smallest value for the projection of A. Do likewise for B.
    1c) Apply the 1-dimensional intersection test using the values from 1b.
    1d) If the test fails (no intersection) then A and B do not intersect.
2. If the 1-dimensional tests never failed, then A and B intersect.

Extending the result
I'm pretty sure that my hypothesis leads to the following general result:

If two shapes intersect, then their projections on every axis intersect.

The converse, however, isn't true because of the following case involving a concave shape:

An Interesting Personal Note
When I was looking into machine learning last summer; I came across the above mentioned concept called linear separability in an article about Support Vector Machines. Now that I think about it, I suppose I've shown that two oriented boxes that don't intersect are linearly separable and that the line separating them is parallel to an edge of one of the boxes. I suppose the above hypothesis involving an equivalence fails only when the two shapes in question are not linearly separable since it should still be possible to find some curve or surface that separates any non-intersecting shapes.

Working on my Problem Solving Episode

I'm not quite done my problem solving episode yet, I'll probably post it it by the end of the weekend.

Not much has actually happened in the last week. The material has recently seemed easy and interesting enough and I finished assignment 3 on the weekend already. I think I've been doing well enough in the course to mostly feel good about everything when I look back. One comment, I feel I ought to make is that these regular expressions seem far more simplified than the ones that some programming languages allow for. In Java's regular expression implementation for example, I see there is the ability to store information (using capturing groups), but I don't think we've learned how to write such expressions in this course.

CSC236 Gets Interesting

The course has gotten pretty cool now that we're learning about these Deterministic Finite State Automata. Interestingly enough, we were learning about stochastic models at around the same time in Statistics and one can see many similarities and differences between these DFSAs and stochastic models such as Markov Chains. Markov Chains are rather like DFSAs that are driven by random strings in which the probability that the next character in the string will be a certain value depends on what state one is in. In both Markov Chains and DFSAs, the previous states that the machine was in don't matter. Likewise, I wonder if some of the techniques we used in Statistics involving transition matrices will crop up in the study of these DFSAs.

I think next week will be the problem solving session, but I haven't yet decided on a good problem to try to solve in it.

Fall Break Edition

I decided to take Fall Break literally and not bother to post until its unfortunate end. In general I have found this algorithm correctness stuff rather challenging, but must admit that it mostly makes sense to me if I actually try applying it myself. I find when I actually attempt to prove correctness that all of the structures we learned about; loop in-variants, preconditions, termination, etc. are all necessary.

Test Tomorrow Edition

Tomorrow we have another test in this course. I find myself in the interesting predicament of admitting that this time complexity-type algorithm analysis stuff hasn't really been all that hard. Instead, I find myself thinking that if there is anything I ought to fear, its this correctness-type algorithm analysis stuff. I've found myself somewhat bamboozled whenever I watched the instructor attempt to teach this correctness stuff to us.

Since we have the test tomorrow, I'm planning on right now reading the course notes to see if I can save myself from the present affliction...

Assignment 2 and Hurricane Edition

Assignment 2 is due at the end of the week. Considering the mark I got on the last assignment, I figure that I have little to fear from it. I would comment, however, that the assignment and tutorial problems have been quite interesting of late. The strategy of solving a problem by developing some sort of algorithm, determining its recursive time formula and then applying the master theorem is pretty neat. As with question 4 from the last assignment, I am using a recursive construction based approach with questions that have a flavour like question 1 from A2.

Having a Bit of Trouble Here

I suppose I had better discuss the following things this week:

1. That last quiz we wrote is probably the first one in which I had no idea how to do the question. Even to this day, I'm a bit confused as to how I should solve a question like that using mathematical induction. I spent the last half an hour trying to figure out how to solve the following question with mathematical induction, which I assume somewhat resembles the one on the quiz:

T(n) = 1 if n < 2
           T(ceiling(n / 2)) + 1 if n >= 2
Prove that T(n) >= clog n for some c > 0 for all n using mathematical induction

To me; this looks like a complete induction type of proof...

Edit: I think I have found a suitable objection to this particular question that would make it slightly impossible to prove it. If some n - 1 is even; then ceil((n - 1) / 2) = ceil(n / 2). This would imply that for some n > 2:

T(n - 1) = T(ceil((n - 1) / 2)) + 1 = T(ceil(n / 2)) + 1 = T(n)

Then if T(n - 1) just happened to be exactly equal to clog(n - 1):

T(n) = T(n - 1) = clog(n - 1)
But clog(n - 1) < clog(n) which means:
T(n) < clog(n).. something that stands in stark contrast to what I would be supposed to prove.

Though, if instead the problem was that one should prove that T(n) > clog n (> not >=) for some c > 0 for all n using mathematical induction; maybe this problem wouldn't happen? Perhaps that was more like the actual problem on the quiz?

Edit 2: So apparently it really was a mistake - you really were supposed to use complete induction and it was just my friend who was confused in thinking there actually was a (reasonable) way to solve it with MI. Perhaps then this quiz should be annulled?

2. Here I suppose I will mention that this algorithm analysis stuff is a vast degree more difficult than the induction stuff we did at the beginning of the course. I suppose I really will need to practice doing some of these questions since it is quite confusing and difficult to visualize how these proofs and such are supposed to work. I am at least a little pleased though with this master theorem and especially with this envelope method, since it means that its possible to use the behaviour of these recursive time functions at certain, easier to prove times (such as when n = 2^k for k within N when dealing with logarithmic recursive functions), to interpolate for the behaviour at the more difficult times in between. I especially found working with floor and ceiling functions to be complicated.