Search code examples
algorithmbounding-boxconvex-hullradix-sort

Minimum axis-parallel bounding box in linear time

Problem
I have to calculate the diameter for a set of 2-dimensional points in linear time O(n).

In order to do this, I thought of using the minimum axis-parallel bounding box that can be computed in linear time with rotating calipers starting from a convex polygon.
Unfortunately I don't have a convex polygon and computing it will require O(nlogn) time because of the convex hull.

My idea was to use the radix sort and then compute the convex hull through monotone chain algorithm (which requires linear time if the input is sorted).

Now my questions are:

  • how can I be sure that radix sort will run in linear time?
  • do you have better ideas to compute the minimum axis-parallel bounding box in linear time?

Thank you in advance!

Edit
I specifically need the minimum bounding box because I have to design a sqrt(2) approximation algorithm for the diameter and this is the only way I know to prove this approximation.

Solution

  • If you're looking for the diameter of a set of points, Welzl's algorithm is probably your best bet. It finds the minimum enclosing circle in linear time.

    EDIT: I didn't realize you needed to make a box. To find the axis-aligned boundary of the minimum bounding box, you'll just want to do a linear scan of your data and take the appropriate min/max values of the (x,y) coordinates.