Largest Ball in a Polyhedron in 2D

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 $${\mathbf 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,
t(a2) %*% x_c + p_norm(a2, 2) * r <= b,
t(a3) %*% x_c + p_norm(a3, 2) * r <= b,
t(a4) %*% x_c + p_norm(a4, 2) * r <= b
)
p <- Problem(obj, constraints)

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

result <- solve(p)
radius <- result$getValue(r) center <- result$getValue(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 / a1, intercept = b / a1) +
geom_abline(slope = -a2 / a2, intercept = b / a2) +
geom_abline(slope = -a3 / a3, intercept = b / a3) +
geom_abline(slope = -a4 / a4, intercept = b / a4) +
geom_circle(mapping = aes(x0 = center, y0 = center, r = radius), color = "blue") +
geom_point(mapping = aes(x = center, y = center), color = "red", size = 2) +
geom_line(mapping = aes(x = c(center, center - radius), y = c(center, center)),
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

sessionInfo()
## R version 3.6.0 (2019-04-26)
## Platform: x86_64-apple-darwin18.5.0 (64-bit)
## Running under: macOS Mojave 10.14.5
##
## Matrix products: default
## BLAS/LAPACK: /usr/local/Cellar/openblas/0.3.6_1/lib/libopenblasp-r0.3.6.dylib
##
## locale:
##  en_US.UTF-8/en_US.UTF-8/en_US.UTF-8/C/en_US.UTF-8/en_US.UTF-8
##
## attached base packages:
##  stats     graphics  grDevices datasets  utils     methods   base
##
## other attached packages:
##  ggforce_0.2.2 ggplot2_3.1.1 CVXR_0.99-6
##
## loaded via a namespace (and not attached):
##   gmp_0.5-13.5      Rcpp_1.0.1        compiler_3.6.0
##   pillar_1.4.1      plyr_1.8.4        R.methodsS3_1.7.1
##   R.utils_2.8.0     tools_3.6.0       digest_0.6.19
##  bit_1.1-14        evaluate_0.14     tibble_2.1.2
##  gtable_0.3.0      lattice_0.20-38   pkgconfig_2.0.2
##  rlang_0.3.4       Matrix_1.2-17     yaml_2.2.0
##  blogdown_0.12.1   xfun_0.7          withr_2.1.2
##  dplyr_0.8.1       Rmpfr_0.7-2       ECOSolveR_0.5.2
##  stringr_1.4.0     knitr_1.23        tidyselect_0.2.5
##  bit64_0.9-7       grid_3.6.0        glue_1.3.1
##  R6_2.4.0          rmarkdown_1.13    bookdown_0.11
##  polyclip_1.10-0   farver_1.1.0      tweenr_1.0.1
##  purrr_0.3.2       magrittr_1.5      MASS_7.3-51.4
##  scales_1.0.0      htmltools_0.3.6   scs_1.2-3
##  assertthat_0.2.1  colorspace_1.4-1  labeling_0.3
##  stringi_1.4.3     lazyeval_0.2.2    munsell_0.5.0
##  crayon_1.3.4      R.oo_1.22.0

R Markdown