Prove Minimum AABB Construction

Question

Assume a point set $P[n]$ with $n$ points which align in one plane in the euclidean space, so $p(x,y) \in \mathbb{R}^2$. Looking for an algorithm to construct an AABB (axis aligned bounding box) I did not find anything. But I thought that the simpliest appraoch could be the best: traverse all $p \in P$ and keep track of the minimum and maximum value of each dimension. The AABB is spanned by the two points $(x_{min},y_{min})$ and $(x_{max},y_{max})$. This clearly runs in $\mathcal{O}(n)$.

Now I struggle proving this kind of obvious fact (the best algorithm runs in $\mathcal{O}(n)$). It is clear that all points of the set have to be checked for inclusion which the algorithm does, given the fact that the set is not preprocessed in any way, like ordered.

What is a good formal approach for proving this?

---

Side note: Is there a better algorithm for constructing an AABB?

Answer 1

Suppose that the points are $(x_1,y_1),\ldots,(x_n,y_n)$. You are looking for the smallest (in some sense) bounding box $[X_m,X_M] \times [Y_m,Y_M]$ containing all your points. For every $i$, we must have $X_m \leq x_i \leq X_M$ and $Y_m \leq y_i \leq Y_M$. In particular, $$ \begin{align*} X_m \leq \min_i x_i =: x_{\min}, \\ X_M \geq \max_i x_i =: x_{\max}, \\ Y_m \leq \min_i y_i =: y_{\min}, \\ Y_M \geq \max_i y_i =: y_{\max}. \end{align*} $$ Summarizing, this shows that every bounding box must satisfy $$ X_m \leq x_{\min} \leq x_{\max} \leq X_M, \\ Y_m \leq y_{\min} \leq y_{\max} \leq Y_M, $$ that is, it must contain $B := [x_{\min},x_{\max}] \times [y_{\min},y_{\max}]$. Conversely, $B$ is itself a bounding box, since $x_{\min} \leq x_i \leq x_{\max}$ and $y_{\min} \leq y_i \leq y_{\max}$ for all $i$. We conclude the following fact:

$B$ is the intersection of all bounding boxes.