# 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.

suppressMessages(suppressWarnings(library(CVXR)))
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 <- 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

library(ggplot2)
library(ggforce)
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

sessionInfo()
## R version 3.5.0 (2018-04-23)
## Platform: x86_64-apple-darwin15.6.0 (64-bit)
## Running under: macOS High Sierra 10.13.4
##
## Matrix products: default
## BLAS: /Library/Frameworks/R.framework/Versions/3.5/Resources/lib/libRblas.0.dylib
## LAPACK: /Library/Frameworks/R.framework/Versions/3.5/Resources/lib/libRlapack.dylib
##
## locale:
## [1] C
##
## attached base packages:
## [1] stats     graphics  grDevices datasets  utils     methods   base
##
## other attached packages:
## [1] ggforce_0.1.1 ggplot2_2.2.1 CVXR_0.99
##
## loaded via a namespace (and not attached):
##  [1] gmp_0.5-13.1      Rcpp_0.12.17      bindr_0.1.1
##  [4] pillar_1.2.2      compiler_3.5.0    plyr_1.8.4
##  [7] R.methodsS3_1.7.1 R.utils_2.6.0     tools_3.5.0
## [10] digest_0.6.15     bit_1.1-13        evaluate_0.10.1
## [13] tibble_1.4.2      gtable_0.2.0      lattice_0.20-35
## [16] pkgconfig_2.0.1   rlang_0.2.0       Matrix_1.2-14
## [19] yaml_2.1.19       blogdown_0.6.3    xfun_0.1
## [22] bindrcpp_0.2.2    dplyr_0.7.5       Rmpfr_0.7-0
## [25] ECOSolveR_0.4     stringr_1.3.1     knitr_1.20
## [28] tidyselect_0.2.4  rprojroot_1.3-2   bit64_0.9-7
## [31] grid_3.5.0        glue_1.2.0        R6_2.2.2
## [34] rmarkdown_1.9.14  bookdown_0.7      udunits2_0.13
## [37] tweenr_0.1.5      purrr_0.2.4       magrittr_1.5
## [40] units_0.5-1       MASS_7.3-50       backports_1.1.2
## [43] scales_0.5.0      htmltools_0.3.6   scs_1.1-1
## [46] assertthat_0.2.0  colorspace_1.3-2  labeling_0.3
## [49] stringi_1.2.2     lazyeval_0.2.1    munsell_0.4.3
## [52] R.oo_1.22.0

R Markdown

## References

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