# Geometric differencing

The diff procedure can be generalized to operate on objects other than strings.
For instance, I imagine that computational geometry asks questions like: "Given two volumes, and allowed only the operations of union and subtraction of volumes, what (shortest) sequence of operations transforms the first volume into the second?"

Seems like to generalize diff beyond strings requires three things: 1) a space of objects on which to operate (these are strings in classic diff, but could be anything like surfaces, volumes, etc).
2) for any object, a decomposition of that object into components, along with an operation -, such that OBJECT1 - COMPONENT := OBJECT2. (e.g. "abcdef" - "de" := "abcf")
3) a binary operation of addition such that OBJECT1 + OBJECT2 = OBJECT3 ("abc" + "def" = "abcdef"). Also, closure under this property.

My questions:
Q1) Can you point me to any concrete incarnations of diff outside the string domain? For instance, what's the name of the computational geometry problem I described in the first paragraph? I'm sure there's extensive literature on this but I just don't know what to google.
Q2) Is there an algebraic structure which fits the structure of generalized diff?

• Would the word problem for groups (or semigroups) qualify as an algebraic instance of "diff"? – mhum Dec 6 '10 at 22:36
• It seems to me you need a fourth thing: 4) a measure of the 'size' of an expression. Otherwise, in many instances diff could trivially return OBJECT2 = (OBJECT1 - OBJECT1) + OBJECT2. In fact, this seems to be a universal answer to your original question whenever the two volumes are distinct (but still possibly overlap). – whuber Dec 7 '10 at 19:02