Improved pointer machine and I/O lower bounds for simplex range reporting and related problems
Peyman Afshani · 2012
We investigate one of the fundamental areas in computational geometry: lower bounds for range reporting problems in the pointer machine and the external memory models. We develop new techniques that lead to new and improved lower bounds for simplex range reporting as well as some other geometric problems.