Problem Statement: Given two points $a$ and $b$ in 3D space and an arbitrary path/curve $S$ (of known length $L(S)$) between the two points, find a tight upper bound for the (euclidean) distance of the midpoint between $a$ and $b$, call it point $c$, and any point $Sp$ on the curve $S$.
So if the euclidean distance between $c$ and $Sp$ is $D(c,Sp)$ and $F(L(S))$ is a function of the path length $L(S)$,
find $F(L(S))$ such that for every $Sp$ that belongs to $S$
$D(c,Sp) \leq F(L(S))$
For example one upper bound I have found is $$D(c, Sp) \leq \frac{L(s)+l}{2}$$ where $l$ is the euclidean distance between points $a$ and $b$ (the end points of the curve $S$).
This is pretty straight forward to prove. Suppose the point on the curve furthest away (in a straight line) from point $c$. Then since $l/2$ is the distance to go from $c$ to either $a$ or $b$ and $L(s)/2$ is the maximum distance one has to travel along the curve $S$ to reach any points of its points (given you can go there from either $a$ or $b$) then the straight line distance of the point on the curve furthest away from $c$ will be equal or less that that.
But I was wondering (and trying to find) if there is an even tighter upper bound.
Context: I am working on an algorithm whereby I want to check weather any of the objects out of a set of $n$ objects, each having a position attribute, lies on a path of known length between two known points $a$ and $b$. The path is divided in $m$ straight line segments (or $m+1$ points if you prefer).
The easiest way of solving this problem is of course to just check each of the $n$ objects against each of the $m$ path segments. This algorithm would be $O(m*n)$ complexity.
But I would like something better (more efficient) so I was thinking if I could find an upper bound as in the problem statement above then I could pre-process the $n$ objects see if they meet the upper bound criterion (this would be $O(n)$ complexity) and then only check those objects that meet the criterion against the m segments (knowing that if they dont meet the upper bound distance limit they could not possibly lie on the path). So if $k$ out of the $n$ objects did NOT meet the criterion then my algorithm would reduce to $O( (n-k)*m )$ complexity. I know that the worst case complexity of the algorithm would still be $O(n*m)$ but I do not expect to hit the worst case complexity often.
I am also aware that I could use spatial data structures to reduce the complexity of the algorithm like a quadtree data structure (this would give $O(n*\log m)$ complexity) but 1) I would like to first explore more simple solutions 2) the quadtree might give me unwanted overhead (the path is dynamic and I would therefore perform insertions/deletions of path segments to the quadtree regularly 3) I just find this problem interesting regardless of weather I will end up using the solution or not :)
At points $A$ and $B$ fix a rope of length $s$, then by the gardener's method draw the ellipse (of course on a given plane through $A,B$).
It is clear that any curve of length $s$ shall lie within that ellipse, i.e. in 3D within its ellipsoid of revolution).
I leave to you to continue, and calculate the distance from $C$, and derive that there cannot be a stricter bound (unless hypothesizing some restriction on the class of functions being considered).