From: sjameson@atl.ge.com (Stephen M Jameson)
Newsgroups: comp.ai
Subject: Re: regions within regions
Date: 13 Aug 92 12:39:08 GMT
Organization: General Electric Advanced Technology Labs

In article <3753@keele.keele.ac.uk> csa09@seq1.keele.ac.uk (Paul Singleton) writes:
> I have some regions in N-space, each defined by a simple set of constraints,
> e.g.
> 	0 =< X =< 5         (1)
> 	0 =< Y =< 5         (2)
> 	2 =< Z =< 7         (3)
> 	0 =< X+Y =< 8       (4)
> 
> and I need an algorithm (for general N) to determine whether one region
> completely encloses another.

This is based on about 5 minutes of pen-pushing, so it may need some smoothing
of the rough edges, but your algorithm will be based on the following three
facts:

1.	Any pair of constraints on different dimensions:

> 	0 =< X =< 5        (1)
> 	0 =< Y =< 5        (2)

Implies a constraint on their sum, which is well defined because of the
limits your problem imposes on definition of the constraints.  In this case, we
have:

	0 =< X + Y =< 10   (5)

2.	Any two constraints:

	a =< X =< b
	c =< X =< d

where X is a single dimension or a sum of dimensions, can be replaced by:

	max(a,c) =< X =< min(b,d)

Thus while constraints (1) and (2) above imply constraint (5), combining
constraints (4) and (5) by the formula above gives constraint (4), i.e.
constraint (4) is "tighter than" or "subsumes" (5).  Thus given any set of
constraints on dimensions, you can eliminate duplicate constraints on the same
dimension or sum of dimensions.

3.	A region A defined by a set of constraints {a_i} is completely enclosed by
another region B defined by {b_i} if and only if:

	a.	All of the dimensions (including sums of dimensions), which are
		constrained {b_i} are also constrained by {a_i}.

	b.	For each constraint in {b_i}, the constraint in {a_i} constraining the
		same dimension or sum of dimensions must be "tighter than" the
		constraint in {b_i}.

Thus we have the following general algorithm:

Given a set of dimensions {X1, X2, .. Xn}, and two sets of constraints,
{a_i} and {b_i}, where each constraint is of the form:

	k1_i <= X_i_1 + ... + X_i_n <= k2_i             (n may be 1)

Step 1.	For each set, using observation 1 above, generate all possible
constraints on sums of dimensions.

Step 2.	For each set, using observation 2 above, eliminate all duplicate
constraints in each set.

Step 3.	For each constraint in {b_i}, verify that there is a constraint in
{a_i} which constrains the same dimension or sum of dimensions and is "tighter
than" the constraint in {b_i}.  If this is the case for all constraints in
{b_i}, then the region defined by {a_i} is completely enclosed by {b_i}.

Each step is fairly straightforward, so I won't generate pseudo-code here.



		
--
Steve Jameson                           General Electric Aerospace 
sjameson@atl.ge.com                     Advanced Technology Laboratories
                                        Moorestown, New Jersey              
****************************************************************************
**  . . . but I do not love the sword for its sharpness, nor the arrow    **
**  for its swiftness, nor the warrior for his glory.  I love only that   **
**  which they defend . . .                                               **
**    -- Faramir, "The Two Towers"                                        **
****************************************************************************
Newsgroups: comp.ai