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.


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;

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

enter image description here


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.


1 Answer 1

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


  • 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"}

enter image description here


  • 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}}.

enter image description here

  • $\begingroup$ I am getting an output that is different. Could this be version related? $\endgroup$
    – Syed
    Commented Feb 23 at 6:31
  • $\begingroup$ @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. $\endgroup$
    – cvgmt
    Commented Feb 23 at 6:37
  • $\begingroup$ 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. $\endgroup$
    – Syed
    Commented Feb 23 at 6:55
  • $\begingroup$ @Syed Maximize[dist@{u,v},{u,v}\[Element]chm] get same result $\endgroup$
    – yode
    Commented Feb 23 at 7:06
  • $\begingroup$ Thanks @yode, it works when r is removed. $\endgroup$
    – Syed
    Commented Feb 23 at 8:01

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.