I'm new to geometric algorithms and computational geometry, so please forgive me if this is an inappropriate question for this forum.

Let $X$ denote the disjoint union of $n$ one-point sets. Let $f:X\rightarrow \mathbb{R}^2$ be a function subject to some set of constraints $C=\{c_1,\cdots,c_m\}$, where $c_i=(x_{i_1},x_{i_2},l_i)$ is a triplet which represents the constraint that $d(f(x_{i_1}),f(x_{i_2}))=l_i$, where $d$ denotes the Euclidean metric on $\mathbb{R}^2$. Suppose $C$ is fixed. I would like to design an algorithm which takes as input an additional constraint, $c'$. The algorithm should efficiently search some representative subset of the space of functions which satisfy the constraints in $C$ to look for one which also satisfies the constraint $c'$. I would be happy with an approximate configuration (i.e. all constraints satisfied within some $\epsilon$).

Has anyone heard of a similar algorithm they can refer me to? I've been browsing the CGAL libraries for something that may be of use to me, but I haven't found anything yet.

  • 2
    $\begingroup$ I don't get it - is $X$ part of the input? If yes, then how should the output depend on $X$? If no, how is your question different from "Given a set of constraints on pairwise distances, find points in the plane satisfying those constraints"? What's the significance of $d$? $\endgroup$ Feb 2, 2016 at 3:19
  • $\begingroup$ I've attempted to make the question more clear. Please see my edits. $\endgroup$
    – beanstalk
    Feb 2, 2016 at 3:52
  • 1
    $\begingroup$ You have changed the terminology, but haven't really answered my questions. Replace $X$ by $f$ and $d$ by $c'$ in my questions to match your new terminology. Perhaps, you could give a tiny example to make it clearer. If you choose to do so, please be explicit, e.g. distinguish clearly what are the inputs and what are the outputs. $\endgroup$ Feb 2, 2016 at 3:58
  • 1
    $\begingroup$ My question is not so different from "Given a set of constraints on pairwise distances, find points in the plane satisfying those constraints?" In fact, I would be happy to hear an approach to doing this. $\endgroup$
    – beanstalk
    Feb 2, 2016 at 4:04
  • $\begingroup$ I suppose the only difference is that it seems to me that any approach taken to answer this question would be iterative, and would therefore require an answer to the more specific one that I have posed. $\endgroup$
    – beanstalk
    Feb 2, 2016 at 4:05


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.