### Abstract

Range searching on categorical, or “colored”, data has been studied extensively for over two decades. In this paper, we obtain the current best results for perhaps the most basic, and most often studied, version of the geometric problem: colored orthogonal range reporting. Given n colored points in two-dimensional space [U]^{2}, we present a data structure with O(n log^{3}/4+^{ε} n) space, for an arbitrarily small constant ε > 0, so that all k distinct colors in any axis-aligned query rectangle can be reported in (optimal) O(log log U + k) time; this is the first method to break the O(nlog n) space barrier. In three dimensions, we present a data structure with O(n log^{9}/5+^{ε} n) space and O(log n/log log n + k) time; this improves the previous space bound of O(n log^{4} n).

Original language | English (US) |
---|---|

Title of host publication | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 |

Editors | Shuchi Chawla |

Publisher | Association for Computing Machinery |

Pages | 627-636 |

Number of pages | 10 |

ISBN (Electronic) | 9781611975994 |

State | Published - Jan 1 2020 |

Event | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 - Salt Lake City, United States Duration: Jan 5 2020 → Jan 8 2020 |

### Publication series

Name | Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Volume | 2020-January |

### Conference

Conference | 31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020 |
---|---|

Country | United States |

City | Salt Lake City |

Period | 1/5/20 → 1/8/20 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Better data structures for colored orthogonal range reporting'. Together they form a unique fingerprint.

## Cite this

*31st Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2020*(pp. 627-636). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms; Vol. 2020-January). Association for Computing Machinery.