# Placing a disk of maximum size in a region surrounded by random points

I start with an array of points (cba) and add randomness to generate (cbar). Four point are deleted from it to generate x and a convex hull is generated named chm.

Clear["Global*"];
SeedRandom[1];

cba = (CoordinateBoundsArray[{{-4, 4}, {-4, 4}}, 1, Center] //
Flatten[#, 1] &) ;
cbar = RandomReal[{-0.25, 0.25}] + # & /@ cba;

x = Complement[cbar, RandomChoice[cbar, 4]];
chm = ConvexHullMesh@cbar;

ListPlot[x
, AspectRatio -> Automatic
, Frame -> True
, Axes -> False
, Epilog -> {FaceForm[Opacity[0.2, Yellow]]
, EdgeForm[Dashed], chm
}
]


Question

How can I identify the emptiest region and put a maximally sized disk there such that no random points are within this disk. The disk also needs to be within the ConvexHullMesh region chm rendered in yellow. Thanks for your help.

This would be similar to 231328 but here I am lacking the polygon and hence the difficulty.

• We union the boundary of convex hull chm and random points x as a single region and use RegionDistance to define a distance function.

Edit

• Use the approach by @yode in comment.
bd = RegionBoundary@chm;
reg = RegionUnion[bd, Point@x];
dist = RegionDistance@reg;
sol = NMaximize[{dist@{u, v}, {u, v} ∈ chm}, {u, v},
Method -> "DifferentialEvolution"]
Graphics[{chm, Red, Point@x, Yellow,
Circle[{u, v} /. Last[sol], sol[[1]]]}]


{1.00713, {u -> -0.694889, v -> 1.49558}}.

• If we don't union the points and the region boundary, it work for both two Methods.
NMaximize[{r, RegionDistance[RegionBoundary@chm, {u, v}] >= r,
RegionDistance[Point@x, {u, v}] >= r, {u, v} ∈ chm}, {u,
v, r}, Method -> #] & /@ {"RandomSearch", "DifferentialEvolution"}


Original

• Method -> "RandomSearch" seems find the maximum r.
bd = RegionBoundary@chm;
reg = RegionUnion[bd, Point@x];
dist = RegionDistance@reg;
sol = NMaximize[{r, dist@{u, v} > r, {u, v} ∈ chm}, {u, v,
r}, Method -> "RandomSearch"]
Graphics[{chm, Red, Point@x, Yellow, Circle[{u, v}, r] /. sol[[2]]}]



{1.00713, {u -> -0.694889, v -> 1.49558, r -> 1.00713}}.

• I am getting an output that is different. Could this be version related?
– Syed
Commented Feb 23 at 6:31
• @Syed I test the code in 12.2,12.3, 13.3.1,14.0 in Windows 11, all the result is 1.00713, ane the Method -> "DifferentialEvolution" give 0.977293. Commented Feb 23 at 6:37
• On the cloud, {0.977293,{u->-0.645305,v->-1.41163,r->0.977293}}  for both DifferentialEvolution and RandomSearch. The circle is situated in the other empty space underneath what you have as the solution. It is quite strange.
– Syed
Commented Feb 23 at 6:55
• @Syed Maximize[dist@{u,v},{u,v}\[Element]chm] get same result
– yode
Commented Feb 23 at 7:06
• Thanks @yode, it works when r` is removed.
– Syed
Commented Feb 23 at 8:01