What is the algebraic structure of all the quadtrees under these operations?

32 Views Asked by At

I was implementing a quadtree in a programming language, and I realized I could define operations such as negation $\bar{x}$, reunion $a\cup b$ and intersection $a \cap b$ on these objects.

These operations have all the propreties of a boolean algebra, but the number of elements is not 2, in fact the set of all elements is not finite.

I think this is equivalent to this situation: you have shapes on the plane with an inside, an ouside and a border. I can take the negation of a shape (the inside became the outside), the intersection of 2 shapes and the reunion of 2 shapes.

To what algebric structure does the set of all possibles shapes under this 3 laws correspond to ?

1

There are 1 best solutions below

5
On BEST ANSWER

There is an algebraic structure also named "Boolean Algebra" which can be defined as a complemented distributive bounded lattice (See the definition here). The "Boolean Algebra" as engineers, programmers, etc. call it (the one with 2 elements) is a special case (indeed a very important one, see here) of this "Boolean Algebra" algebraic structure.

Note: In the definition linked above, there are two special elements of $A$ called $0$ and $1$. It is important, then, to emphasize in the definition that $A$ may contain more than just $0$ and $1$! These 2 special elements are just specified in the definition because they are used the axiom of complements $a\wedge\neg a=0$ and $a\vee\neg a=1$. In the shape analogy, $0$ and $1$ correspond to the "empty" shape, and the "whole plane" shape, respectively.