0
$\begingroup$

Given n disks in the plane, i want to compute the lowest point in their intersection area, im looking for a simple randomized incremental algorithm.

There are some circles in the plane, these circles have an intersection R, the point with the lowest y in R is what i mean.

Why i thought of RIC is that maybe we can add circles incrementaly and updating the intersection area each time and also the optimal point should be updated if it possible with the lower time.

I think this problem have some similarity with 2D half-plane intersection (2D LP). In that problem we were looking for an optimal point in respect of the cost vector. But subproblems in that problem was finding the intersection between a half-plane and a convex region with can be reduced to a simpler 1D problem. That 1D problem is half-line intersection, which is easier to solve.

Here but i have trouble to define a simpler subproblem. Also in the Analysis for expected time, i don’t see how to use backward analysis here.

I also guess maybe we can solve this problem with finding the convex-hull of those circles, then we look for it’s core with half-plane intersection, but i really uncertain about this idea.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ Please don't leave clarifications in the comments. Instead, edit your question so it is clear and reads well for someone who encounters it for the first time. Please define what is meant by "lowest point" in this context. It might help to tell us the context or motivation; where did you encounter this problem? Why do you think that a randomized algorithm is appropriate? $\endgroup$
    – D.W. ♦
    Commented May 12, 2021 at 20:14
  • $\begingroup$ Idea: The boundary of the intersection of a set of circles is a cycle of arcs belonging to the circles, which can be represented by angular intervals (note that a single circle can contribute more than one arc). Adding a new circle adds zero or more new arcs, which can be determined by looking for intersections with the existing arcs in the cycle. Each new arc added cuts off zero or more existing arcs. The intersection's minimum y coord must be achieved either at the arc endpoint having minimum y coord, or at a point tangent to a horizontal line in the arc on either side of it. $\endgroup$
    – j_random_hacker
    Commented May 18, 2021 at 3:25

1 Answer 1

Reset to default
0
$\begingroup$

I suspect you should be able to solve this with a sweepline algorithm, probably in $O(n \log n)$ time or something like that.

In particular, I suggest you build a data structure so that for any $x$, you can find the range of $y$-values that are in the intersection of all the circles. You should be able to build such a data structure by mimicking the Bentley-Ottmann algorithm. Decompose each circle into four quarter-circles (arcs that cover one-fourth of the perimeter of the circle). Each quarter-circle takes the place of a line segment. Each intersection between two quarter-circles is an "event". Then it is easy to answer your original question; each interval of $x$ values between two consecutive events corresponds to a single leaf in the tree, and you can quickly compute the lowest $y$ value in the intersection for that range of $x$ values, then do that for each such interval. I haven't tried to work through all the details, so I suggest you check the specifics to see if this works out or if there is some challenge I've overlooked.

Improve this answer
$\endgroup$
2
  • $\begingroup$ You mean - in $O(n \log n)$ time, right? $\endgroup$
    – HEKTO
    Commented May 21, 2021 at 22:10
  • $\begingroup$ @HEKTO, oops, yes, that's what I meant. Edited. Thank you. $\endgroup$
    – D.W. ♦
    Commented May 21, 2021 at 22:15

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.