5
$\begingroup$

Are algorithms already known, that generate (arbitrarily good approximations of) random curves, w.l.o.g. with unit length, and joining endpoints $(0,0)$ and $(\alpha,0)$ with $\alpha \lt1$ given?

The fixed distance between the endpoints is essential for the question, because otherwise a simple rescaling of an arbitrary curve would work.

edit

In view of the comments and the answer of Bjørn Kjos-Hanssen, I see the need for some clarification:

  • By random curve of unit length connecting $(0,0)$ and $(\alpha,0)$, I mean a random sample from the space of all such curves; that means, that the algorithm should be capable to approximate every such curve to arbitrary precision with a finite number of steps.
    So "random" is not restricted to the appearance of the curve.

  • Being able to generate Brownian Bridges is not sufficient, because I would like the algorithm to be able to generate curves (ideally in any $\mathbb{R}^n$) and not only functions.

So my apologies for not being precise enough.

I have used the formulation "are algorithms already known", because I have found one, that seems to be able to produce all those curves.

I will provide details in a later edit.


Here are the promised details:

the algorithm, that motivated this question is essentially based on realizing, that no point of the curve can lie outside the ellipse centered at $\left(\frac{\alpha}{2},0\right)$, foci $p$ at $\left(0,0\right)$ and $q$ at $\left(\alpha,0\right)$, for which the length of the semi-major axis equals $\frac{1}{2}$ and, $\sqrt{\left(\frac{1}{2}\right)^2-\left(\frac{\alpha}{2}\right)^2}$ for the semi-minor axis.
If the intermediate curve-point $r$ is chosen from the boundary of that ellipse, then the "length-stock" is used up and the algorithm terminates with a curve consisting of two line-segments and exact length $1$, joining $p$ and $q$ as demanded.

Otherwise the length-stock is split up and assigned to two newly generated line-segments and the original problem of finding a curve of fixed length with endpoints at fixed has to be solved recursively for both segments separately.

Pseudo code:

$\text{expand}$(Point $p$, Point $q$, Length $\ell$, Curve curve)

$\quad$Point $r\in \lbrace x\in\mathbb{R}^n\ |\ \| r-p \| + \|q-r\|\ \le \ell\rbrace$;
$\quad$Length $\ell_{pr}$ := $\|r-p\|$;
$\quad$Length $\ell_{rq}$ := $\|q-r\|$;
$\quad$Length $\Delta\ell$ := $\ell-\left(\ell_{pr}+\ell_{rq}\right)$;
$\quad$Scalar $a\in\left[0,1\right]$

$\quad$if (a < threshold)
$\quad\quad$curve.append($r-p$);
$\quad$else
$\quad\quad\text{expand}$($p$,$\ r$,$\ \ell_{pr}$+$a$ * $\Delta\ell$);

$\quad$if ($1-a$ < threshold)
$\quad\quad$curve.append($q-r$);
$\quad$else
$\quad\quad\text{expand}$($r$,$\ q$,$\ \ell_{rq}$+(1-$a$) * $\Delta\ell$);

Some remarks:

the pseudo code is aimed at full generality and also covers "degenerate" cases; those need to be ruled out by further checks. One such case is the collinearity of $p$, $\ q$ and $r$ with positive $\Delta\ell$.

Selecting $r$ from the mentioned elliptical regions with foci $p$ and $q$ can also be interpreted as chosing one of the intersection points of a circle around $p$ and $q$. That covers the algorithm of Matt F. as a special case.

The followup challenge is now to control further properties of the curve via taylored rules for selecting $r$ and distributing $\Delta\ell$ on each recursion level.
Or, play with the options to discover interesting curves and fractals.

$\endgroup$
  • $\begingroup$ Do you require any smoothness? Because otherwise you can take a Brownian bridge as pointed out by Bjorn's answer. $\endgroup$ – Henry.L Apr 25 '17 at 17:08
  • 4
    $\begingroup$ What set of random curves do you have in mind (differentiable, ...?), and what kind of probability measure? $\endgroup$ – Ben Crowell Apr 25 '17 at 17:08
  • $\begingroup$ Why not let the midpoint of the curve be a random point within (curve length/2) of both the starting point and the end point, and then iterate? $\endgroup$ – Matt F. Apr 25 '17 at 17:30
  • $\begingroup$ What space of curves are you referring to and with what distribution? It is easy to sample from "reasonable" distributions of curves with two fixed end points. For example, one can pick N points at random in the plane and then smoothly interpolate between them using cubic Hermite splines or something. It really depends on what you need these curves for. $\endgroup$ – Izaak Meckler Apr 26 '17 at 5:34
  • $\begingroup$ @IzaakMeckler how would you ensure the fixed distance between the endpoints of the curve, when picking points at random and interpolate by "something"; that only works in a trial and error manner. The set of curves with fixed length and endpoint-distance is "static"; therefore asking for its distribution misses something; I agree however that asking for the distribution of the "points" generated by the sampling process, would make sense - that should be taken care of by adjusting parameters during the execution of the algorithm. $\endgroup$ – Manfred Weis Apr 26 '17 at 6:38
5
$\begingroup$

One approach is to let the midpoint of the curve be a random point within (curve length)/2 of both of the starting point and the end point, and then iterate. For curves of length 1 between (0,0) and (1/2,0) that gives results like this:

three random curves

In more detail, to connect a starting point and ending point by a curve of length $2c$, draw circles of radius $c$ about both points, and randomly pick a point in the intersection to be the midpoint of the curve. So from the points at distance 0 and 1 on the curve, calculate the point at distance 1/2, and then the points at distance 1/4 and 3/4, etc. For the pictures above, I went down to distance 1/1024, picking points in the inscribed rhombus rather than the curved shape to simplify the algebra.

diagram

I have no reference for this, but I believe that with probability 1 it generates curves of length 1. I've attached the Mathematica code for a curve in a comment if you want to play with it.

$\endgroup$
  • $\begingroup$ base = c {t, u}/Sqrt[t^2 + u^2]; vecs = {x, y} - base /. Simplify[Solve[x^2 + y^2 == c^2 == (x - t)^2 + (y - u)^2, {x, y}], Assumptions -> u > 0]; mid[c_, p_, q_, {r_, s_}, {t_, u_}] = {r, s} + base + p vecs[[1]] + q vecs[[2]] /. {t -> t - r, u -> u - s}; f[Rational[m_, n_]] := f[m/n] = mid[1/n, Random[], Random[], f[(m - 1)/n], f[(m + 1)/n]]; f[0] = {0, 0}; f[1] = {0.5, 0}; curve = Map[f, Range[0, 1, 1/1024]]; ListLinePlot[curve, AspectRatio -> Automatic] $\endgroup$ – Matt F. Apr 28 '17 at 20:59
4
$\begingroup$

Here are some random "scribbles," based on Bjørn Kjos-Hanssen's idea (but not following his specifications exactly), mixing with Izaak Meckler's comment:


RWalks
What you see is points of a random walk fit with cubic Bézier curves with $C^1$ continuity.

$\endgroup$
  • $\begingroup$ DId you generate it by urself ? If so, can you please provide a script. Thank you. $\endgroup$ – koryakinp Feb 21 at 21:37
  • $\begingroup$ @koryakinp: I just generated a random walk, unit step length, and then used Mathematica's Spline[pts,Cubic] function. $\endgroup$ – Joseph O'Rourke Feb 21 at 21:41
3
$\begingroup$

How about starting with a Brownian bridge $B_t$; then make it smooth and having finite length by convolution $g_t=B_t*f$; and then multiplying by a constant to get a unit length curve $c g_t$?

$\endgroup$
  • $\begingroup$ The Brownian bridge could be multi-dimensional by the way, so it's not 'only functions'... $\endgroup$ – Bjørn Kjos-Hanssen Apr 26 '17 at 7:09
  • $\begingroup$ Ok, agreed. I had to look up Brownian Bridge in the internet and got the impression, that it is a function. I will however leave my clarification, that I am not only looking for graphs of curves with functional dependence of $y(t)$ on $x(t)$ $\endgroup$ – Manfred Weis Apr 26 '17 at 8:12
  • 2
    $\begingroup$ By the way, does the scaling in your construction for smooth curves preserve endpoint distance? That is a point I do not quite understand. $\endgroup$ – Manfred Weis Apr 26 '17 at 8:16
2
$\begingroup$

Defining $z_t(s)=\int_0^s e^{itu(\sigma)}\ d\sigma$ transforms any function $u$ : $(0,1) \to \mathbb R$ into a one-parameter family of length $1$ curves $C_t=\{z_t(s):\ 0\leq s\leq1\}$ whose distance between end points should initially decrease from $1$, and shrink to $0$ as $t\to\infty$ (provided $u\neq0$ a.e.).

This may not qualify as an "algorithm" though, since the choice of $t$ to get the proper length remains implicit.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.