Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How do you determine if you can draw a circle around a set of points, such that the points from the other set aren't inside it?

I am wondering about an algorithm that returns true or false, telling me if it's possible to draw a circle around a set of points A, such that any point from the set of points B is not inside it, or the other way around (possible to draw a circle around a set of points B, such that any point from the set of points A is not inside it).

Basically, you are given 2 sets of points as input, and you need to determine if it's possible to draw a circle around either one, such that any point from the other isn't inside it.

I have looked at Megiddo's linear time algorithm for the smallest enclosing circle problem, but the problem is that it only draws the smallest circle, which means it doesn't work in the case where you need a large circle.

Here's a pic of what I mean:

enter image description here

In this picture it's possible to draw a very large circle around the set of red points, so that any one of the green points aren't inside it, hence Megiddo's algorithm won't work.

like image 853
Pavel Avatar asked Jun 06 '15 19:06

Pavel


1 Answers

In this paper, we reduce detecting whether or not two sets of points in the plane can be separated by a circle, to linear separability of points in 3D:

O'Rourke, Joseph, S. Rao Kosaraju, and Nimrod Megiddo. "Computing circular separability." Discrete & Computational Geometry, 1.1 (1986): 105-113. (PDF download.)

like image 82
Joseph O'Rourke Avatar answered Oct 07 '22 01:10

Joseph O'Rourke