Given a set ofnpoints in the plane, we can find the minimum area triangle in quadratic time, but the best known lower bound is onlyOmega(n log n). Find a subquadratic algorithm, or prove a quadratic lower bound in any model of computation.This problem is clearly 3SUM-hard, since it's harder than finding colinear triples in the plane. Thus, a subquadratic algorithm seems unlikely. I have established quadratic lower bounds for the colinear points problem in several (slightly) different models of computation, but the minimum-area triangle problem cannot even be solved in the models in which my lower bounds hold.

In

ddimensions, the minimum volume simplex can be found inO(ntime and^{d})O(nspace, but again, the best known lower bound is only^{2})Omega(n log n).Leonid Khachian [J. Complexity 11:138-163 (1995)] shows that, if the dimension is not fixed, finding the minimum volume simplex, or even approximating its volume to within a factor of

2, is NP-hard.^{poly(n,d)}[This is the problem that first led me to study lower bounds. I'm not much closer to a solution than when I started!]

Given a set ofnpoints in the complex plane, how quickly can we determine whether any three lie on a complex line? (Recall thatC^{2}is isomorphic toC^{2}, and a complex line is isomorphic to a 2-flat. Every triple of points inR^{4}lie on a 2-flat, but not all these flats are isomorphic to complex lines.) There is a simple algorithm that runs in timeR^{4}O(n. The challenge is to get rid of the log factor in the running time. There is a quadratic-time algorithm for the corresponding problem over the reals, but it does not generalize to the complex case.^{2}log n)On the other hand, the best known lower bound for this problem is only

Omega(n log n). The challenge here is to increase the lower bound toOmega(nin any reasonable model of computation. The problem is clearly 3SUM-hard, since it's harder than the corresponding problem over the reals. I have established a quadratic lower bound for the real problem, but the complex problem cannot even be solved in the models in which my lower bound holds.^{2})

Given a set of

npoints in, for someR^{d}d>3, determine whether or not every point is a vertex of the set's convex hull. The best known algorithm for this problem, developed by Timothy Chan using results of Jíri Matousek, runs in timeExcept for the polylog factor, this algorithm is almost certainly optimal, but the best known lower bound is only

O(n^{2 floor{d/2} / (floor{d/2}+1)}polylogn).Omega(n log n). Prove a better lower bound in any model of computation, or derive a significantly faster algorithm.This question is (probably) related to the polytope questions on the other page.

Given a sorted list ofnreal numbers, find the smallest interval containing exactlykelements, for all values ofkbetween 1 andn. There is a simple dynamic programming algorithm that solves this problem in quadratic time, but the best known lower bound is only linear. Either describe a faster algorithm, or prove a bigger lower bound in some reasonable model of computation. ("Dynamic programming" is not a reasonable model of comptuation!!)

Given a set of lines in the plane, and letsandtbe two vertices of its arrangement. How quickly can we find the shortest path fromstotalong the edges of the arrangement? There is an easyO(n-time algorithm, but the best lower bound is only^{2}log n)Omega(n log n), by reduction from convex hull size verification. Is a subquadratic algorithm possible?The problem is open even in the special case where the lines form two pencils, and the source and target points are corners of the distorted grid they form. See the figure. A straightforward dynamic programming algorithm runs in quadratic time. Either describe a faster algorithm, or prove a bigger lower bound in some reasonable model of computation. (Again, "dynamic programming" is not a reasonable model of computation!!)

Bose, Evans, Kirkpatrick, McAllister, and Snoeyink have an approximation algorithm that runs in

O(n log n)time and finds a path at most twice as long as the shortest path.Of course, similar questions can be asked about arrangements of line segments. David Eppstein and David Hart recently derived an algorithm that finds shortest paths in an arrangement of axis-parallel segments in

O(ntime. See "An efficient algorithm for shortest paths in vertical and horizontal segments", Proc. 5th WADS (Lecture Notes in Comput. Sci. 1272), pp. 234-247, 1997.^{3/2})

Open Problems - Jeff Erickson (jeffe@cs.duke.edu) 05 Sep 97