# 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

## 2 Answers

In the realm of constructive solid geometry, questions like the one you asked can probably be answered. Here, solids are constructed by unions and differences of basic shapes (for example, a sphere with a tunnel can be described as Ball - Cylinder. Shapes are then built up as trees of operations on basic shapes (at the leaves), and the differencing problem can then be thought of as a labelled tree-diff problem (which has been examined among other things in the context of comparing XML documents).

I'm not claiming that these questions are already being studied, but CSG is definitely one place where the geometric questions you're asking might be addressed.

I think little is known about such questions because they are immediately in the NP-hard domain. As a concrete example, consider the problem of deciding given a set in the plane (with piecewise linear boundaries), what is the minimal number of triangles needed to cover it. However, after appropriate twiddling, this is minimum set cover of points in the plane by triangles, which is hard. And this is maybe the simplest variant of such a problem.

Another way of thinking about this problem (which is hand-wavy and just intuition, but nevertheless...), is that you are trying to find the simplest description of a decision surface that separates some set of points from another. And that is, in general, a very hard problem...