Skip to main content
4 of 9
merged "answer" with question (and made it more of a question; removed the imperative mood)
Todd Trimble
  • 53.3k
  • 6
  • 205
  • 322

On some optimal containers of a set of points on the 2D plane

Given a set of N points in general position on the plane, the problem is to give efficient algorithms to find

  1. the smallest semicircular region (semidisk) that contains the points
  2. the smallest circular segment that contains the points (2 variants - 'smallest' could mean either of 'least area' or 'least perimeter').
  3. the smallest sector that contains the points (again, 2 variants)

I am not aware of previous works on these questions. I am seeking relevant pointers to the literature.

Full disclosure: I proposed an O(N^2) algorithm for question 1 in https://arxiv.org/abs/2005.10245. No proof of optimality was given, so there could be faster algorithms.

Some thoughts on question 2 are also given there but no algorithm.

Nandakumar R
  • 6k
  • 3
  • 7
  • 20