Partition into almost straight trails

Let G=(V,E)G=(V,E) be a graph that is embedded in the plane, i.e. VV is a finite vertex set of points in the plane and the edge set EE is represented as a set of (straight-line) segments in the plane with endpoints from VV. A trail   is a sequence T=(e1,…,ek)T=(e1,…,ek) of pairwise distinct edges such that there are vertices v0,…,vkv0,…,vk with ei=vi−1viei=vi−1vi for i∈{1,…,k}i∈{1,…,k}. Consecutive edges of a trail form an angle in the plane and with each such angle αα we assign a geometrically motivated value z(α)z(α). The weight of TT is defined as the sum of these zz-values. We study the problem of partitioning the graph into trails, i.e. decomposing the edge set of the graph into a disjoint union of edge sets of trails, such that the sum of their weights is maximal. We reduce the problem to a matching problem on the circle and present an efficient matching algorithm. The problem is motivated by an application in image processing.