The session began with discussion concerning the posting on the Web of the substance of exploration of open questions.
Most of the remainder of the session was occupied with variations of a question posed by guest presenter Giri Narasimhan. The problem is a clustering problem: covering a set of points by a fixed number of boxes.
One version is trivial, but it can easily be modified to be as difficult as desired.
EASIEST VERSION: Input: a set of n points S in the plane Output: the smallest axis-aligned rectangle that contains S
The answer can be found in O(n) time by scanning S for the extremal coordinates.
If a different axis is given, one can simply translate to the new coordinate system, also in O(n) time.
SECOND VERSION: Input: a set of n points S in the plane Output: the two smallest rectangles that contains S
'Smallest' may be taken as smallest area, perimeter or major dimension.
The problem may be generalized by increasing the number of boxes or by increasing the number of dimensions. Joe Mitchell referred to a paper on the two-box, d-dimension case by Sergei Bespamyatnikh and Michael Segal
http://www.dgp.toronto.edu/cccg/cccg97/papers/30/30.html
Joe said paper's results pertain to a class of minimization functions which include the maximum dimension and sum of areas, but not sum of union of areas of the boxes.
Some time was spent discussing the version in which the restriction on the alignment of the bounding boxes is dropped.
THIRD VERSION: Input: a set of n points S in the plane Output: the two smallest rectangles that contains S
Joe said he and a student are working on 3D rectilinear case to achieve some reasonable polynomial result, say <2.
In 2D, they have a O(n) solution for two rectilinear boxes, but it requires a highly non-trivial method to 'search the matrix.'
Steve suggested the case where there are k rectangles permitted.
Joe thought this is related to the 'two-center problem', i.e., to cover a set of points with two circles, minimizing either the sum or the maximum of the radii. David Epstein has published the best randomized result in SODA. Micah Sharit has a non-randomized n polylog time result.
Some time was spent looking at the problem by fixing the amount of time available for the computation. For example, if one is looking for a linear time procedure, what is the best coverage by bounding boxes that is available?
Giri suggested that the most productive approach might be a geometric one, for example building on the idea of well-separated pair decomposition.
Callahan and Kasaraju have results which find clustering points using this technique in O(n log(n)) time.