Algorithm for dividing in half multiple points using a circle with a fixed radius

Question

Suppose I have a set of points in a Cartesian plane defined by an array / coordinate vector (X, Y). This set of points will be “adjacent” in the coordinate plane if any set of discontinuous points can be adjacent. That is, these points arose as a rectangular grid in which the areas of the points were eliminated using the previous algorithm. The shape indicated by dots is arbitrary, but it will have arcs for the edges.

Suppose further that I can create circles with a fixed radius r .

I need an algorithm that will find me the center of X,Y for a circle that will be as close as possible to half of the points indicated.

Answer 1

OK, try this (sorry if I have a very poor wording: I did not study math in English)

Step 1: Find the axis

• For all pairs of points that are less than 2p apart , count how many points lie on both sides of the connecting line
• Choose a pair with worse balance
• Calculate the line that halves these two points as an axis ("The axis of greatest concavity")

Step 2: Find a Center

• Start on the far axis (> 2r) on the side that had the bottom point count in step 1 (concave side)
• Move the center along the axis until you reach the desired point. This can be done by moving in increments of sqrt (delta), where delta is the smallest distance between two points in the set, if the overload moves halfway back, etc.

Answer 2

You might want to study the smallest circle environment of a point set .

A somewhat greedy algorithm would be to simply remove points 1 at a time until the radius of the circle is less than or equal to r.