# Fitting curves with restricted relative orientations

## Edited to focus on the math (thanks whuber):

Given a sequence $$z_1,…,z_n$$ of complex numbers and a fixed real number $$σ$$, find a sequence $$x_1,…,x_n$$ from the set $$\{0,\pm1,\pm2\}$$ minimizing $$\sum_{j=1}^n|s_j-z_j|^2$$

where $$s_j=\sum_{k=1}^j\exp(ix_k\sigma)$$

$$σ=(5/180)π$$

The real problem is in 3D space and the available set for $$x_n$$ depends on the value of $$x_{n-1}$$. But I think solving this simplification will help lead me in the right direction.

## Original:

I have a curve that I need to best-fit (least deviation/error) using fixed-length lines whose orientation depends on the orientation of the previous line segment. As a simplification from 3D to 2D, you can think of segment N+1 as having the following possible orientations:

• [Orientation of Segment N] - 10-deg
• [Orientation of Segment N] - 5-deg
• [Orientation of Segment N]
• [Orientation of Segment N] + 5-deg
• [Orientation of Segment N] + 10-deg

Therefore, the orientation of segment N+2 is dependent on N+1 as well as N.

Consider a scenario where the best-fit is made up of 3500 line segments and each segment can be in one of up to 26 orientations relative to the segment before it. 26^3500 combinations is too large to evaluate all options. I can approach the problem starting at line segment 0 and best-fitting each subsequent segment resulting in 26*3500 combinations, which can be achieved in a reasonable amount of time (say 10 minutes), but this does not yield the optimal result.

I can also look-ahead Y segments and best fit N+1,N+2...N+Y segments at a time. This is more compute-intensive but is feasible for up to a lookahead of about 4 segments. The issue is that this is also not the optimal fit.

I can demonstrate that by making the fit of segment N non-optimal, I can improve the fit at segment N+500, and reduce the overall error of the system. Note that changing the orientation of Segment N requires recomputing segment N through segment 3500, because they are all dependent on the segment before them.

How can I optimize this fitting scenario?

I feel like I am missing the correct words to use for research on this topic.

Edit: Additional sketch showing an example of the relative/physical constraints between line segments. Simplified further to only allow +5 or -5 relative orientation between adjacent segments.

Edit: The physical system being modeled are the pre-cast tunnel lining rings erected behind tunnel boring machines. The machine is attempting to follow a desired alignment, to the lowest overall error. The rings are fixed geometry, installed in contact with the previous ring, and can be installed in discrete positions (in this example 26 positions). Examples of these consecutive geometries are shown in some images in this blog (not mine): https://geo-technical.blogspot.com/2014/05/week-18-tunnelling-tbm-course-ground.html

• Re "Therefore, the orientation of segment N+2 is dependent on N+1 as well as N": how does that follow? Your description is that the orientation of each segment is "relative to the segment before it." How would any information about the orientations of any preceding segments provide any more information? Perhaps you could describe the original problem rather than explaining the issues you have with a purported solution.
– whuber
Commented Jan 11 at 23:24
• The relative orientation between line segments is restricted to {10,5,0,-5,-10} degrees due to the physical system the optimization is simulating. If Segment N is oriented at 0 degrees, the global orientation of Segment N+1 is {10,5,0,-5,-10} (0 + relative orientation). Instead, if N is oriented at 5 degrees, the global orientation of N+1 is {15,10,0,-5} (5 plus relative orientation). The black/red/purple lines in the sketch show how relative orientations accumulate to effect the global orientation of the line. Commented Jan 12 at 1:23
• One would guess that: but could you articulate the problem you are trying to solve? Would it be to approximate a given curve with the cumulative sum of such segments? If so, why? How does such a constraint arise? (That is, is the constraint inherent in the problem or is it induced by an attempt to solve a different problem?) The apparent contradictions in your statement are puzzling, too. For instance, how does the set $\{\pm10,\pm5,0\}$ translate to "26 orientations"?
– whuber
Commented Jan 12 at 12:20
• The physical system being modeled are the pre-cast tunnel lining rings erected behind tunnel boring machines. The machine is attempting to follow a desired alignment, to the lowest overall error. The rings are fixed geometry, installed in contact with the previous ring, and can be installed in discrete positions (in this example 26 positions). Examples of these consecutive geometries are shown in some images in this blog (not mine): geo-technical.blogspot.com/2014/05/… Commented Jan 12 at 14:16
• $n$ is fixed within a couple percent. Because the curve $t$ is designed to work with the segments, the best-fit follows the curve close enough that the length of curve divided by the length of segments is $n$ $n=len(curve(t)) / len(s_J)$. The increments $|z_{j+1}-z_j|$ should be approximately equal to the segment length. I had missed the relationship between $e^x$ and angle. Commented Jan 12 at 18:18