# Intersection/Union of Rectangles as a Group (or Monoid or…?)

In a computer graphing library, a rectangular region of the Cartesian plane may be defined by {x, y, w, h} (where w,h are width and height). Intersection (lets say '^') is defined as the overlapping region of two rectangles (and also is a rectangle). Union of r1 and r2 could be defined as the smallest (ie smallest w, smallest h) rectangle 'u' such that u ^ r1 = r1 and u ^ r2 = r2

etc.

My question(s):

• does negative w, h make 'sense',
• if so , what sense does it make? ie, and in particular, should the result of intersection of non-overlapping rectangles be a rectangle with negative width and/or height?
• can this be used to build a Group over the set of rectangles with the operation of union and/or intersection?

• what is the 'area' of a rectangle with width < 0 and height < 0. I would like it to be negative, but typically it is width x height, thus positive.

Sorry if this sounds more computerish than mathish, but I was once a math major, and non of the other computerish people I might ask know anything about group theory...

More thoughts:

I want to decide if rectangles with negative dimensions makes much sense. I could leave this up to the users of the rectangles, but it is up to me to define what an operation like intersection does.

'neg' rectangles could just mean that the x,y is at the opposite corner than expected. ie they could be 'facing' the wrong way, and by moving x,y to the opposite corner, w,h can be made positive, and the rectangles are 'normalized'.

But when I consider intersection, imagine 2 rectangles moving along the plane, at first intersecting, but moving such that they overlap less and less - they eventually get to the point where they only touch at the corners - and the intersection is then a rectangle with w = h = 0.

Now, If we continue to move the rectangles further apart, you could either say that the result of intersection is still an empty rectangle, or I think it might make more sense to say the result is a 'negative' rectangle (and w,h depicts how far away they are from overlapping).

Given this concept, can it be somehow continued/followed/expanded in a logical/consistent way, and if so, what do we end up with?

Mathematically it would nice if it was a group, and if making it a group required a few other common operations (like union maybe) to be defined in a certain consistent way, I would like to explore that.

I just don't have any colleges nearby that think mathematically...

-
Any definition that you could want to make depends on what you want the definition to do for you. What purpose do you want this to serve? –  Qiaochu Yuan Mar 1 '10 at 20:01
I'd say that what the union/intersection allows you to do is to define a lattice (i.e., a poset with finite meets and joins) in the set of rectangles. I haven't checked but you might get a monoid by considering the endomorphisms of the lattice, which you could then turn into a group using the Grothendieck construction. I don't see, though, how this is related to rectangles with negative dimensions. –  José Figueroa-O'Farrill Mar 1 '10 at 20:02
You are not going to get a group (independently of what you decide to do with negative widths and heights), because you already have problems with cancellation: the union of {x:0, y:0, w:1, h:1} with {1, 1, 1, 1} is the same as the union of {0,0,2,1} with {1, 1, 1, 1}, namely {0, 0, 2, 2}. A similar thing happens with intersections. –  Mariano Suárez-Alvarez Mar 1 '10 at 20:06
I'll update the quesiton with a few more thoughts... –  tony Mar 1 '10 at 20:11
I apologize if you were already aware of this - it is hard to tell from what you've said - but a group has just one operation. –  Zev Chonoles Mar 1 '10 at 20:18

I imagine the only useful way of interpreting a rectangle with negative w and/or h should just be as a rectangle with positive width and height, only starting at a different point (it's lower left vertex, it seems?).

With either union or intersection as the operation, you're going to run into a couple of problems if you want the structure to be a group. The only possible choice for the identity under intersection is the entire plane (which, if you are parametrizing the rectangles in the plane using (x,y,w,h), would require you to allow x=y= $-\infty$, w,h=$\infty$), and the only possible choice for the identity under union is an "empty" rectangle (i.e., w=h=0, though you'll also have the problem that there is one of these at each x and y). Of course, given any rectangle which is not the entire plane, you can't take an intersection of it with something and get the entire plane, and similarly, given any rectangle which is non-empty, you can't take the union of it with something and get an empty rectangle - that is, there won't be inverses. However, as you guessed in the title, you still do get a commutative monoid.

You can make a group (and even ring) structure, similar to what you are describing, out of the collection of all subsets of the plane (or any set), as described here, but you'd have to give up your restriction to only rectangles if you want to use this one, because the operation used is the symmetric difference.

EDIT: This is to summarize the things you seem to be looking for:

• The set of rectangles in the plane, under the operation of intersection, makes a commutative monoid if you allow for the "infinite rectangle" consisting of the entire plane.
• Unfortunately, under union (as you defined it for rectangles - least rectangle containing both), there is in fact no identity, because given any two distinct "empty" rectangles, let's say the ones at (a,b) and (c,d), their "union" would be the rectangle with opposite corners at (a,b) and (c,d) and so is non-empty, so neither of them can be an identity. Thus, the set of rectangles in the plane, under the operation of "union", is only a commutative semigroup.
• The set of rectangles is not closed under taking symmetric difference or the usual union.

That describes the situation with the main set-theoretic operations, though you may be able to construct another operation on rectangles using some combination of addition and multiplication on the parameters (x,y,w,h) which makes a stronger structure.

-
Interesting thoughts, thanks. –  tony Mar 1 '10 at 20:30