Current Status
The only known lower bound for any d is . The Overmars–Yap algorithm provides an upper bound of, so for d ≥ 3, it remains an open question whether faster algorithms are possible, or alternatively whether tighter lower bounds can be proven. In particular, it remains open whether the algorithm's running time must depend on d. In addition, the question of whether there are faster algorithms that can deal with special cases (for example, when the input coordinates are integers within a bounded range) remains open.
Read more about this topic: Klee's Measure Problem
Famous quotes containing the words current and/or status:
“The current of our thoughts made as sudden bends as the river, which was continually opening new prospects to the east or south, but we are aware that rivers flow most rapidly and shallowest at these points.”
—Henry David Thoreau (1817–1862)
“At all events, as she, Ulster, cannot have the status quo, nothing remains for her but complete union or the most extreme form of Home Rule; that is, separation from both England and Ireland.”
—George Bernard Shaw (1856–1950)