3
$\begingroup$

Question 1: Why we can/can't solve the following problem using a geometric constraint solver?
Question 2: Is there any algorithm to solve this problem?
Question 3: Can we reduce this problem into some known computational problems?

Input:
1. $C_1, ..., C_n$: Centres of $n$ circular rings.
2. $S$: A polygon of arbitrary shape in the 2D plane.

Notations:
1. $(OR_i, IR_i)$: outer radii and inner radii respectively for circular ring $i$
2. $R = \text{ring}_1 \cap \dots \cap \text{ring}_n$: the intersection of the rings (i.e., the region of space formed by their intersection: the set of points that are contained in all $n$ of the rings)

Output:
Find $(OR_1, IR_1),..., (OR_n, IR_n)$, such that region $R$ covers the polygon $S$ with minimal error area.

Error area is defined as: $$\text{Area}(S - R) + \text{Area}(R -S)$$

Intuitively, I want an algorithm to find optimal $(OR, IR)$ for each ring to cover a given shape $S$, so the error area (the parts of $R$ outside the given shape: [$\text{Area}(R - S)$] + the parts of the shape not covered by $R$: [$\text{Area}(S - R)$]) is minimal.

The problem differs from this problem in following ways:

  1. The polygon should be covered by the ring formed by two circles with same centre.
  2. This is a simpler problem in the sense that it has fewer variables. The position of the centres are given; we only need to find the inner and outer radii.
Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

This problem might be hard to solve exactly. I would suggest you try gradient descent (or another mathematical optimization technique).

[ The stuff below here is obsolete, now that the question has been edited to change the problem statement along these lines. ]

Note that minimizing your error ratio is equivalent to minimizing

$$\text{Area}(S-R) + \text{Area}(R-S),$$

since $S$ is given (so $\text{Area}(S)$ is fixed). This observation does not seem to help very much, though.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I have looked at the gradient descent algorithm. Apparently, you need an error function which will be reduced in each iteration, until its minimized. The main difficulty here is to define this error function. We need to get a measurement of the difference between the actual polygon S and the shape formed by the intersection of the rings, R. Any idea on how we can define this difference? $\endgroup$
    – Mamun
    Commented Aug 14, 2015 at 1:44
  • 1
    $\begingroup$ @Mamun, I suggest you spend some more time looking at gradient descent, since it sounds like there are some misconceptions in your comment. Gradient descent minimizes an objective function. You pick the objective function. Here the objective function to use is the error area -- so you already know how to define it; it's exactly the error area that you defined in your question. $\endgroup$
    – D.W. ♦
    Commented Aug 14, 2015 at 1:46
  • 1
    $\begingroup$ @Mamun, it's not difficult to define the objective function. You already defined it in the question: the objective function is $\text{Area}(S - R) + \text{Area}(R -S)$. All you need is an algorithm to compute that value, as a function of $S$ and $(OR_1,IR_1),\dots,(OR_n,IR_n)$. If you're asking how to compute it, that's a different question, which you should ask separately. You certainly will need to figure out how to compute that before you can even imagine trying to find $R$ that minimizes this value. $\endgroup$
    – D.W. ♦
    Commented Sep 2, 2015 at 20:35

Your Answer

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

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