Research output: Contribution to book/anthology/report/proceeding › Article in proceedings › Research › peer-review

- Timothy M. Chan, School of Computer Science, Canada
- Bryan Thomas Wilkinson

Close Abstract

We present three new results on one of the most basic problems in geometric data structures, 2-D orthogonal range counting. All the results are in the w-bit word RAM model.

•It is well known that there are linear-space data structures for 2-D orthogonal range counting with worst-case optimal query time O(log_w n). We give an O(n loglog n)-space adaptive data structure that improves the query time to O(loglog n + log_w k), where k is the output count. When k=O(1), our bounds match the state of the art for the 2-D orthogonal range emptiness problem [Chan, Larsen, and Pătraşcu, SoCG 2011].

•We give an O(n loglog n)-space data structure for approximate 2-D orthogonal range counting that can compute a (1+δ)-factor approximation to the count in O(loglog n) time for any fixed constant δ>0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem.

•Lastly, we consider the 1-D range selection problem, where a query in an array involves finding the kth least element in a given subarray. This problem is closely related to 2-D 3-sided orthogonal range counting. Recently, Jørgensen and Larsen [SODA 2011] presented a linear-space adaptive data structure with query time O(loglog n + log_w k). We give a new linear-space structure that improves the query time to O(1 + log_w k), exactly matching the lower bound proved by Jørgensen and Larsen.

We present three new results on one of the most basic problems in geometric data structures, 2-D orthogonal range counting. All the results are in the w-bit word RAM model.

•It is well known that there are linear-space data structures for 2-D orthogonal range counting with worst-case optimal query time O(log_w n). We give an O(n loglog n)-space adaptive data structure that improves the query time to O(loglog n + log_w k), where k is the output count. When k=O(1), our bounds match the state of the art for the 2-D orthogonal range emptiness problem [Chan, Larsen, and Pătraşcu, SoCG 2011].

•We give an O(n loglog n)-space data structure for approximate 2-D orthogonal range counting that can compute a (1+δ)-factor approximation to the count in O(loglog n) time for any fixed constant δ>0. Again, our bounds match the state of the art for the 2-D orthogonal range emptiness problem.

•Lastly, we consider the 1-D range selection problem, where a query in an array involves finding the kth least element in a given subarray. This problem is closely related to 2-D 3-sided orthogonal range counting. Recently, Jørgensen and Larsen [SODA 2011] presented a linear-space adaptive data structure with query time O(loglog n + log_w k). We give a new linear-space structure that improves the query time to O(1 + log_w k), exactly matching the lower bound proved by Jørgensen and Larsen.

Original language | English |
---|---|

Title of host publication | Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013 |

Editors | Sanjeev Khanna |

Number of pages | 11 |

Publisher | Society for Industrial and Applied Mathematics |

Publication year | 2013 |

Pages | 241-251 |

ISBN (print) | 978-1-61197-251-1 |

ISBN (Electronic) | 978-1-61197-310-5 |

DOIs | |

Publication status | Published - 2013 |

Event | ACM-SIAM symposium on Disrete Algorithms - New Orleans, United States Duration: 6 Jan 2013 → 8 Jan 2013 Conference number: 24 |

Conference | ACM-SIAM symposium on Disrete Algorithms |
---|---|

Nummer | 24 |

Land | United States |

By | New Orleans |

Periode | 06/01/2013 → 08/01/2013 |

To appear in: SODA’13: 24th Symposium on Discrete Algorithms

See relations at Aarhus University Citationformats

ID: 69901553