Largest Ball in a Polyhedron in 2D

Author

Anqi Fu and Balasubramanian Narasimhan

Problem

The following is a problem from Boyd and Vandenberghe (2004), section 4.3.1.

Find the largest Euclidean ball (i.e. its center and radius) that lies in a polyhedron described by affine inequalites:

$P = x : a_{i}^{'} * x <= b_{i}, i = 1, . . ., m$

where x is in $R^{2}$ .

We define variables that determine the polyhedron.

a1 <- matrix(c(2,1))
a2 <- matrix(c(2,-1))
a3 <- matrix(c(-1,2))
a4 <- matrix(c(-1,-2))
b <- rep(1,4)

Next, we formulate the CVXR problem.

r <- Variable(name = "radius")
x_c <- Variable(2, name = "center")
obj <- Maximize(r)
constraints <- list(
    t(a1) %*% x_c + p_norm(a1, 2) * r <= b[1],
    t(a2) %*% x_c + p_norm(a2, 2) * r <= b[2],
    t(a3) %*% x_c + p_norm(a3, 2) * r <= b[3],
    t(a4) %*% x_c + p_norm(a4, 2) * r <= b[4]
)
p <- Problem(obj, constraints)

All that remains is to solve the problem and read off the solution.

result <- psolve(p)
check_solver_status(p)
radius <- value(r)
center <- value(x_c)
cat(sprintf("The radius is %0.5f for an area %0.5f\n", radius, pi * radius^2))

The radius is 0.44721 for an area 0.62832

A Plot

ggplot() +
    geom_abline(slope = -a1[1] / a1[2], intercept = b[1] / a1[2]) +
    geom_abline(slope = -a2[1] / a2[2], intercept = b[2] / a2[2]) +
    geom_abline(slope = -a3[1] / a3[2], intercept = b[3] / a3[2]) +
    geom_abline(slope = -a4[1] / a4[2], intercept = b[4] / a4[2]) +
    geom_circle(mapping = aes(x0 = center[1], y0 = center[2], r = radius), color = "blue") +
    geom_point(mapping = aes(x = center[1], y = center[2]), color = "red", size = 2) +
    geom_line(mapping = aes(x = c(center[1], center[1] - radius), y = c(center[2], center[2])),
              arrow = arrow(length = unit(0.03, "npc"), ends = "first", type = "closed"),
              color = "brown") +
    annotate("text", x = -0.2, y = 0.04, label = sprintf("r = %0.5f", radius)) +
    labs(x = "x", y = "y") +
    xlim(-1, 1) + ylim(-1, 1)

Session Info

R version 4.5.2 (2025-10-31)
Platform: aarch64-apple-darwin20
Running under: macOS Tahoe 26.3

Matrix products: default
BLAS:   /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRblas.0.dylib 
LAPACK: /Library/Frameworks/R.framework/Versions/4.5-arm64/Resources/lib/libRlapack.dylib;  LAPACK version 3.12.1

locale:
[1] en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8

time zone: America/Los_Angeles
tzcode source: internal

attached base packages:
[1] stats     graphics  grDevices utils     datasets  methods   base     

other attached packages:
[1] ggforce_0.5.0   ggplot2_4.0.2   CVXR_1.8.0.9215

loaded via a namespace (and not attached):
 [1] gmp_0.7-5.1        generics_0.1.4     clarabel_0.11.2    slam_0.1-55       
 [5] lattice_0.22-9     digest_0.6.39      magrittr_2.0.4     evaluate_1.0.5    
 [9] grid_4.5.2         RColorBrewer_1.1-3 fastmap_1.2.0      rprojroot_2.1.1   
[13] jsonlite_2.0.0     Matrix_1.7-4       ECOSolveR_0.6.1    backports_1.5.0   
[17] scs_3.2.7          Rmosek_11.1.1      scales_1.4.0       tweenr_2.0.3      
[21] codetools_0.2-20   cli_3.6.5          rlang_1.1.7        polyclip_1.10-7   
[25] Rglpk_0.6-5.1      withr_3.0.2        yaml_2.3.12        otel_0.2.0        
[29] tools_4.5.2        osqp_1.0.0         Rcplex_0.3-8       checkmate_2.3.4   
[33] dplyr_1.2.0        here_1.0.2         gurobi_13.0-1      vctrs_0.7.1       
[37] R6_2.6.1           lifecycle_1.0.5    htmlwidgets_1.6.4  MASS_7.3-65       
[41] pkgconfig_2.0.3    cccp_0.3-3         pillar_1.11.1      gtable_0.3.6      
[45] glue_1.8.0         Rcpp_1.1.1         xfun_0.56          tibble_3.3.1      
[49] tidyselect_1.2.1   knitr_1.51         dichromat_2.0-0.1  highs_1.12.0-3    
[53] farver_2.1.2       htmltools_0.5.9    labeling_0.4.3     rmarkdown_2.30    
[57] piqp_0.6.2         compiler_4.5.2     S7_0.2.1

References

Boyd, S., and L. Vandenberghe. 2004. Convex Optimization. Cambridge University Press.