Imagine three sets of planes (A, B, and C). The planes in each set are parallel and evenly spaced and so can be defined by a plane equation and a scalar representing the distance between planes. If all three of these sets were orthogonal (as a contrived example) then by computing the intersections of all the planes somehow, it would generate a lattice consisting of an edge anywhere that any two planes intersect and a vertex at any point where three planes intersect. Assume that I am generating this lattice over a finite bounding volume (let's just make it a cube for simplicity and assume the set of planes exist within said cube). I can easily brute-force solve this by intersecting the sets of planes two sets at a time (i.e. AB, BC, and AC) generating a set of edges and then finding the intersections of each edge with every other edge, but this algorithm would be O(really bad).

I would like to find the lattice generated by an arbitrary number of sets of planes where each set contains parallel planes that are uniformly spaced (although the spacing for each set is arbitrary). I would like to do this in O(decent) if that's possible. I know that I can break this problem down exactly the same way and solve for pairs of planes and then intersect all the edges but this problem gets worse and worse as the number of planes increases. I feel like I can probably solve this more easily by transforming every set of planes into a single plane that intersects the origin, finding the intersecting lines, then intersecting all of those lines and then generating the rest of the lattice since I know the spacing of vertices (if any) on each line will correspond to the distance along that line between the planes for each set (which is again known since the spacing is constant for each set) but this would still be inefficient for an arbitrary number of planes. I'm willing to accept that this is just a hard problem to solve and that brute-forcing it may be my only option but I figured that I'd ask in case anyone has any insight on how I can make this better somehow.

Also, it is safe to ignore the case where the sets of planes never intersect at all or only intersect along an edge. The application of this problem is model synthesis (relevant paper if anyone is interested: http://gamma.cs.unc.edu/synthesis/papers/constraint.pdf)


1 Answer 1


enter image description here

Something like: $ (x-1)(x-3)(x-5) = 1/100 $ , $ (y-4)(y-7)(y-10) = 1/100 $, $ (z-1)(z-4)(z-7) = 1/100 $ ?

  • $\begingroup$ Oh, you want to compute the intersection to store line segments by pairwise intersection, and points by triple intersection? $\endgroup$
    – Alan
    Mar 28, 2014 at 20:18
  • $\begingroup$ Yes, I need the line segments and points, although the points may be the intersection of more than three planes. Just the edges and vertices from the thing you rendered there. I also need to ensure that I know which line segments and which planes are associated with each vertex $\endgroup$ Mar 28, 2014 at 21:20
  • $\begingroup$ Mathematica statement that brings up 27 points in a list: NSolve[(x - 1) (x - 3) (x - 5) == 1/100 && (y - 4) (y - 7) (y - 10) == 1/100 && (z - 1) (z - 4) (z - 7) == 1/100, {x, y, z}] ---- How big would the table be,? Can it be computed once and stored? $\endgroup$
    – Alan
    Mar 28, 2014 at 21:32
  • $\begingroup$ Yes this is a pre-computation step so I can store it easily. The table could potentially be massive also, and the spacing between the planes is only guaranteed to be the same within a single set; different sets could be spaced completely differently. I'm really not seeing much besides a divide-and-conquer approach that involves computing intersections of small numbers of planes and then merging the results. I could use many systems of linear equations and solve them all too, but it seems like that would be just as inefficient. I'm hoping there's some sort of clever shortcut solution $\endgroup$ Mar 28, 2014 at 22:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .