@inproceedings{429d2c894605460c83109b758e3f3c81,

title = "Optimal halfspace range reporting in three dimensions",

abstract = "We give the first optimal solution to a standard problem in computational geometry: three-dimensional halfspace range reporting. We show that n points in 3-d can be stored in a linear-space data structure so that all k points inside a query halfspace can be reported in O(log n + k) time. The data structure can be built in O(n log n) expected time. The previous methods with optimal query time required superlinear (O(n log log n)) space. We also mention consequences, for example, to higher dimensions and to external-memory data structures. As an aside, we partially answer another open question concerning the crossing number in Matou{\v s}ek's shallow partition theorem in the 3-d case (a tool used in many known halfspace range reporting methods).",

author = "Peyman Afshani and Chan, {Timothy M.}",

year = "2009",

doi = "10.1137/1.9781611973068.21",

language = "English (US)",

isbn = "9780898716801",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery (ACM)",

pages = "180--186",

booktitle = "Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms",

address = "United States",

note = "20th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 04-01-2009 Through 06-01-2009",

}