# Matching the segments of a set to longer segments of another set

Consider a set $$S$$ of segments in the plane. Split each segment in $$S$$ into a few pieces, and slightly modify the extremities of each obtained segment (by adding a small random value to their coordinates, e.g.). Then consider the set of all obtained segments and add to this set a number of random segments. This gives a new (larger) set $$S'$$ of segments.

Given $$S$$ and $$S'$$, how to find the segments in $$S'$$ that (most probably) come from the pieces of segments in $$S$$? and how to find the segment in $$S$$ from which they were (most probably) obtained?

• Do you have information on the random values' distribution? And how are the random segments generated? To me the problem lacks information to be formalized. Also, how are segments expressed? E.g. pairs with starting point and ending point? Or lines with extremes on one coordinate? The solution depends on several factors Commented Aug 28, 2023 at 14:07
• What do you call "a few pieces" exactly ?
– user16034
Commented Aug 28, 2023 at 14:13
• @SilvioM I do not really have information on the random values, but they do not change segments enough to make them drastically different from what they were (otherwise the problem could not be solved). The random segments may be sampled uniformly at random among the ones with the same length distribution as the other segments in $S'$, and in the same part of the plane as them. And each segment is encoded by the coordinates of its endpoints indeed. Commented Aug 28, 2023 at 17:58
• @YvesDaoust $S'$ and $S$ are probably disjoint, so $S'$ is not much different from $S'\setminus S$. And "a few pieces" may be something like 2 to 10 pieces. Commented Aug 28, 2023 at 18:00
• @YvesDaoust Sorry if this was unclear, but $S'$ is a completely new set built from $S$ without its elements, only (modified) "pieces" of them and random segments. Commented Aug 28, 2023 at 18:06

Here is a simple approach:

1. Let $$E$$ denote all the endpoints of $$S$$.

2. Find all segments in $$S'$$ that have an endpoint near a point of $$E$$.

3. For each such segment $$s' \in S'$$ with an endpoint near $$e \in E$$, test whether $$s'$$ is close to a portion of some segment in $$S$$. If it is, output it, remove $$e$$ from $$E$$, and add the other endpoint of $$s'$$ to $$E$$.

4. Go to step 2.

Step 2 can be implemented efficiently using a nearest-neighbor data structure. Step 3 can be implemented efficiently as well: associate each endpoint $$e \in E$$ to its corresponding segment $$s \in S$$; then given $$e$$, you can find the other endpoint of $$s'$$, call it $$f$$, and test whether $$f$$ is close to the line $$s$$.

• Simple indeed but rather elegant, thanks. Commented Aug 28, 2023 at 18:10

Take all "new" segments in turn and compute a distance to the initial segments. Associate a new segment to the closest "old".

For the distance you might consider the average distance of every point of a segment to another, or to the line of support of the other.

• I think this solution, besides being a "brute force" approach, does not address the problem of random segments added in $S^{\prime}$ Commented Aug 28, 2023 at 14:35
• @SilvioM: right, a Q&D solution is to set a maximum distance.
– user16034
Commented Aug 28, 2023 at 14:39

One possible approach which will both solve the problem of detecting random segments from $$S^{\prime}$$ and associate original and modified segments is that of doing a nearest neighbor search of original segments in $$S$$ inside the new segments in $$S^{\prime}$$. In this way, you find for each original segment the closest one inside $$S^{\prime}$$ and the elements of $$S^{\prime}$$ which are not associated to any original segment at the end of the procedure are the random ones. You may exploit something like sweep line algorithm or kd-trees in some way to enhance the search and avoid a simple naive search.

For doing that you need to define a metric on segments, e.g. the average of the distances between left-most extremes and right-most extremes (i.e. you compare the two extremes with the smallest $$x$$ coordinate and the two with the biggest $$x$$ coordinate).

Keep in mind that this solution may give you totally wrong results. Indeed, it is impossible to associate modified segments to original ones without additional information on random modifications' distribution and magnitude, random segments' distribution and original segments' distributions.

• Thanks. Is this consistent with the fact that several original and modified segments (the "pieces") in $S'$ may be associated to a same original segment in $S$? Commented Aug 28, 2023 at 18:04
• @MatthieuLatapy it all depends on random modifications, of course it can't be consistent with your request in general. In order to avoid two modified segments are associated to the same original one, you can simply flag the already assigned segments so that you don't take one sogment more times. Another possibility is that of assigning a global score, like for instance in k-means clustering algorithm (e.g. the average error) and look at the assignment which minimizes the average error Commented Aug 29, 2023 at 10:58