Counting targets by their holes

Every earlier essay here has used the Euler characteristic to describe one shape at a time: $V - E + F = 2$ for a convex solid, $0$ for a solid with a tunnel through it, and in the last essay the constraint it puts on which counts a solid can have. This essay uses it differently — not as a property of a shape but as a way of measuring collections of shapes, the way area measures them.

The reason it can be used that way is that it adds. Put two shapes together, and the Euler characteristic of the union is the sum of theirs minus that of their overlap — exactly the rule that area obeys, and that counting obeys, which inclusion–exclusion turned into a method. Anything that adds like that can be integrated against. And integrating against the Euler characteristic turns out to solve a problem that area cannot: counting overlapping objects from local counts alone.

Pieces minus holes #

For a shape in the plane built from squares, the Euler characteristic is computed exactly as for a solid: count the corners, subtract the edges, add the squares, with every corner and edge shared between squares counted once. The answer has a simple meaning: the number of separate pieces, minus the number of holes.

The raw counts are large and depend on every detail of the shape — the disc has 185 corners, 340 edges and 156 squares — and the combination is small and depends on nothing but how the shape is connected. That insensitivity is what every corner pays for itself proved for solids: subdivide a face, and the new corners, edges and faces cancel exactly. Here the subdivision is the grid, and any grid fine enough to capture the shape’s pieces and holes gives the same answer. Two trees and every edge gave the cleanest reason for that invariance on a solid: the edges split into a tree through the corners and a tree through the faces, and a tree always has one more corner than edges. For a flat shape the same argument, with the outside of the shape playing the part of one extra face, gives one for each piece and minus one for each hole.

And every surface is a sphere with handles is the statement that for closed surfaces this one number, with orientability, is a complete description. For flat shapes it is not complete — a disc and a square have the same characteristic, as do two discs and a disc beside a square — but it is complete enough to count, and counting is what the rest of this essay does with it.

The flat and the solid cases are one rule. In the plane, the characteristic is pieces minus holes; for a solid’s surface, it is two for each separate piece minus two for each tunnel. In both, the number is decided by how the shape is connected and not by its size or its exact outline, and in both it is computed by the same alternating count of corners, edges and faces. That is the property the rest of this essay exploits: a quantity that is additive like area and yet blind to area.

It adds like an area #

The additivity is worth checking on a case where it is not obvious, because the union of two shapes can have holes that neither has.

Neither ring has more than one hole, but their union has three: each ring’s own hole, and a new one enclosed between them where they cross. The union’s characteristic, $1 - 3 = -2$, is not visible in either ring. Yet it follows from the rings and their overlap alone: $\chi(A \cup B) = \chi(A) + \chi(B) - \chi(A \cap B) = 0 + 0 - 2$. The overlap’s two pieces have exactly accounted for the new hole and for the fact that the two rings, which were two pieces, have become one.

This rule is called being a valuation. Area is a valuation, perimeter is a valuation, and so is the Euler characteristic; Hugo Hadwiger proved in 1957 that, for reasonable shapes and up to scaling, these are the only valuations in the plane that do not change when a shape is moved about, and every other one is a combination of them. Of the three, the Euler characteristic is the only one that ignores size entirely. Scale a shape up by any factor and its area grows by the square of the factor, its perimeter by the factor itself, and its Euler characteristic not at all.

Integrating against the Euler characteristic #

Anything that adds can be integrated. Area gives the ordinary integral: to integrate a function that takes whole-number values, add up, for each level $k$, the area of the region where the function is at least $k$. The Euler characteristic gives an integral in exactly the same way:

$$\int h \, d\chi = \sum_{k \ge 1} \chi\bigl(\{\,x : h(x) \ge k\,\}\bigr).$$

The ordinary integral of the sensor counts adds up areas — and for a count made by overlapping regions, it gives the sum of the regions’ areas. The Euler integral adds up Euler characteristics instead, and by additivity it gives the sum of the regions’ Euler characteristics. The step deserves one line of justification. The count $h$ is a sum of indicator functions, one for each region, and an integral of a sum is the sum of the integrals, for the Euler integral exactly as for the ordinary one — additivity is all that is used. The integral of one region’s indicator is the region’s own Euler characteristic, since its only nonempty level set is the region itself. So the Euler integral of the count is the sum, over regions, of their characteristics, however the regions overlap; the overlaps are handled by the additivity and never need to be seen. If each region is a disc, or any shape in one piece with no holes, each contributes exactly 1, and the Euler integral of the count is the number of regions.

This was the observation of Yuliy Baryshnikov and Robert Ghrist in 2009, built on the integration theory developed by Oleg Viro and Pierre Schapira in the late 1980s. The problem it solves is concrete. A field of cheap sensors can each detect whether targets are nearby and how many, but not identify them or say where they are; each target is detected in some region around it; and the regions overlap. How many targets are there?

The same trick on a line #

The idea is clearest in one dimension, where it can be done in the head. Put some intervals on a line, overlapping in any way, and at each point record how many intervals cover it. From those coverage counts alone, how many intervals were there?

The ordinary integral of the count is the total length of the intervals — useless without knowing their lengths. The Euler integral adds up, for each $k$, the number of separate pieces of the region where the count is at least $k$, since an interval’s Euler characteristic is 1 and a union of disjoint intervals has characteristic equal to the number of pieces. And that sum is the number of intervals, whatever their lengths and overlaps.

A small case shows why. Two intervals overlapping in the middle: the region with count at least 1 is one piece, the region with count at least 2 is one piece, and $1 + 1 = 2$. Two intervals side by side, not touching: count at least 1 is two pieces, count at least 2 is empty, and $2 + 0 = 2$. Three intervals all overlapping one point: $1 + 1 + 1 = 3$. The pieces at each level trade off exactly, and in one dimension there is a direct way to see it: the number of pieces of $\{h \ge k\}$ is the number of times the count steps up from $k - 1$ to $k$ reading left to right, and summing over $k$ counts every step up — one at each interval’s left end.

In two dimensions there is no “left end”, and the holes that overlaps create have to be subtracted; the Euler characteristic is exactly the bookkeeping that does it.

Seven targets, found in the counts #

The opening figure is that problem, solved. Seven discs of different sizes overlap in a complicated pattern, and each sensor reports how many contain it. Adding the counts gives 744, the total area of the discs in squares, which would count the targets only if the discs’ areas were known. The Euler integral needs no such knowledge.

The level sets tell the story. The region where the count is at least one is the whole union of the discs, a single piece with no holes: characteristic 1. The region where it is at least two — where two or more discs overlap — has characteristic 0: pieces and holes cancel. The regions where it is at least three and at least four hold the remaining six between them, as scattered islands where many discs pile up. None of those numbers is the number of targets, and none of the level sets looks like seven of anything. Their sum is exactly seven.

The mechanism is inclusion–exclusion running in the background. Each overlap between two discs creates, in the level set above it, an extra island; each ring of overlaps creates a hole; and the Euler characteristic weights islands and holes with exactly the signs needed to cancel everything except one unit for each disc. No sensor needed to know which target it saw. And no sensor needed to know anything about its neighbours beyond their counts: the level sets are built from the readings, and their Euler characteristics are computed from which neighbouring squares share a level. The whole count is assembled from information each sensor could broadcast in a single number.

Where it fails, exactly as predicted #

The method assumes each target’s detection region has characteristic 1: one piece, no holes. When that assumption fails, the answer changes by exactly the amount the theory says.

A ring has characteristic 0, so each ring-shaped region contributes nothing to the Euler integral, and three targets become invisible. The failure is not noise and not an approximation; it is the theorem, applied to regions it was not designed for. If the regions are known to be rings, the fix is equally exact — each contributes 0, so count something else — and in general the method counts targets weighted by the characteristic of their detection regions, which must be known in advance.

That is the honest statement of what the method needs: not the regions’ sizes, not their positions, not their shapes, but their topology. For most physical detection — a sensor that detects anything within some range, blocked by nothing — the region is a disc or a deformed disc, and the count is right. Where something blocks the view — a wall between some sensors and a target — the region can acquire holes or split in two, and the count is off by exactly the change in characteristic; knowing the obstacles, that change can be computed and corrected.

Pieces, holes and the turning of a boundary #

There is a third way to compute the same number, and it connects the first of these essays to the last. Walk round the boundary of a shape in the plane, keeping it on the left, and add up how much the direction of walking turns — positively at convex corners, negatively at reflex ones. For a disc the total is one full turn, $360°$. For a ring there are two boundaries: the outer one turns $+360°$ and the inner one, walked with the shape on the left, turns $-360°$, for a total of zero. In general the total turning is $360°$ times the Euler characteristic.

That is the flat version of seven hundred and twenty degrees of gap: the angle defects at the corners of a convex solid add up to $720°$, which is $360°$ times its characteristic, 2. Both are cases of the Gauss–Bonnet theorem, which says that the total curvature of a surface, or the total turning of a curve round a region, is fixed by topology alone. So the Euler characteristic can be measured locally, corner by corner, by adding turning angles — which is exactly how image-analysis software computes it for scanned shapes, from the configurations of two-by-two blocks of pixels along boundaries, a method Stephen Gray published in 1971.

This local computability is the reason Euler integration is practical at all. Each sensor, or each small group of neighbouring sensors, can contribute its local share of the Euler characteristic of each level set from what it and its neighbours see, and the shares add up across the whole field to the global answer — without any sensor knowing where the targets are or how the regions are shaped. The count is assembled from purely local information, like area, and yet measures something no local quantity seems to know about.

In materials science the same three valuations — area, perimeter and Euler characteristic, the complete list Hadwiger found — are used to describe the structure of foams, porous rocks and alloys from micrographs, under the name Minkowski functionals: the first two measure how much material there is and how much surface, and the third how the pores are connected.

What the picture cannot show #

The figures compute everything on a grid, where each sensor is a square, and on a grid the Euler characteristic depends on a convention about edges: when two squares that are counted by different targets share an edge, does the edge belong to both regions or to neither? The figures use the convention that makes the arithmetic exact — each region is the open set inside its squares, and edges and corners count only when every square around them is in the region — and with that convention the Euler integral equals the number of discs exactly. With the other convention, a pair of discs that merely touch along an edge creates a thin sliver of overlap that nobody drew, and the count can come out wrong by one.

That is not a quirk of the figures but the real practical difficulty. Real sensors are sparse points, not a tiling, and the level sets have to be reconstructed from samples; if the sampling is too coarse to capture the overlaps’ holes and islands, the integral is off. Baryshnikov and Ghrist’s method is exact in the continuum and approximate on data, and the error depends on how densely the sensors sample the regions’ topology.

Still open: Euler integration with noise and motion #

The theory is complete for fixed targets and exact sensors, and extends to moving targets, where the counts change in time and the integral must be taken over time as well as space. What is not settled is how it behaves on real data. Sensor counts are noisy — a sensor may miss a target or count one twice — and the Euler characteristic, which depends only on topology, is exquisitely sensitive to single errors that create or fill a hole. How to make Euler integration robust, while keeping the property that it needs no knowledge of the regions’ sizes, is an active question, and the answers so far combine it with the tools of persistent homology, which measure how long each hole survives as a threshold changes.

A deeper open question is how much more topology can count. The Euler characteristic is the only valuation that ignores size, so it is the only one that can count regions of unknown size; but targets could be counted by other features if the sensors reported more than a single number. Which sensor readings allow which quantities to be recovered, and at what cost in sensors, is a question at the boundary between topology and signal processing that has only begun to be mapped.