Given $n \geq 2$ points in the plane, how can one efficiently (or even inefficiently!) compute the number of corner-points belonging to the boundary of the intersection of the unit disks centered on those points? (This number is 0 when the intersection of the disks is empty and 2 or more otherwise, leaving aside measure-0 cases in which the intersection is a single point or a disk.)
$\begingroup$
$\endgroup$
2
asked Feb 10, 2021 at 0:30
-
1$\begingroup$ What if we have a single disk? $\endgroup$– markvsCommented Feb 10, 2021 at 0:38
-
$\begingroup$ Good point! I'll reword. $\endgroup$– James ProppCommented Feb 10, 2021 at 0:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
7
I think this can be accomplished in $O(n \log n)$ time by a sweep-line algorithm, but it might not be worthwhile implementing to achieve that asymptotic complexity. Likely an incremental algorithm is easiest. Just maintain a representation of the intersection, a convex region bounded by circular arcs, and intersect with the next circle, update, and repeat.
I couldn't find an algorithm description in the literature, except the following, whose focus is more on wireless communication than on disks intersection.
Librino, Federico, Marco Levorato, and Michele Zorzi. "An algorithmic solution for computing circle intersection areas and its applications to wireless communications." Wireless Communications and Mobile Computing 14, no. 18 (2014): 1672-1690. arXiv abs.
Incidentally, the much more difficult problem of computing the intersection of unit balls in $\mathbb{R}^3$ can be achieved in $O(n \log^2 n)$ time.
answered Feb 10, 2021 at 1:23
-
1$\begingroup$ Can the boundary of the new disk intersect the boundary of the intersection of the old disks more than twice (outside of the degenerate case in which all the disks are the same disk)? Note that this can happen if the disks have different radii, but when they all have radius 1 I don’t see how to make this happen. $\endgroup$ Commented Feb 10, 2021 at 14:58
-
$\begingroup$ @JamesPropp: That does seem to be true. Likely could be proved by studying the arrangement of the centers. $\endgroup$ Commented Feb 10, 2021 at 15:31
-
$\begingroup$ @JamesPropp: This seems to hold for unit disks: A disk contributes an arc to the intersection only if its center lies on the convex hull of all the disk centers. This would then lead to a simple algorithm, constructing that hull. $\endgroup$ Commented Feb 12, 2021 at 1:45
-
1$\begingroup$ See mathoverflow.net/questions/383709/… for a discussion of the question of whether there can be more than two points of intersection of the boundaries. (If my conjecture from that other post is true, then my conjecture here would follow. The hypothesis of smoothness of the boundary is inessential, since points of non-differentiability can be smoothed without destroying any intersections.) $\endgroup$ Commented Feb 12, 2021 at 3:29
-
$\begingroup$ @JamesPropp: If the hull hypothesis holds, then the "at most two points of intersection" should follow from one new disk center adding two new edges to the hull. Not that I've proved this, but it seems plausible. $\endgroup$ Commented Feb 12, 2021 at 11:21