## Abstract

In many scientific fields, it is common to encounter raster data sets consisting of categorical data, such as soil type or land usage of a terrain. A problem that arises in the presence of such data is the following: given a raster G of n cells storing categorical data, compute for every cell c in G the number of different categories appearing within a window centered at c. The window can either be a (2r+1)x(2r+1) square or a disk of radius r for a positive integer parameter r. We call this the categorical richness problem, and we present two algorithms for it: one for square windows that runs in O(n) time and one for circular windows that runs in O((1+K/r)n) time, where K is the number of distinct categories in G. The algorithms are not only efficient in theory, but also in practice: our experiments show that our algorithms can handle raster data of hundreds of millions of cells.

The categorical richness problem is related to colored range counting, where the goal is to preprocess a colored point set such that we can efficiently count the number of colors appearing inside a query range. We present a data structure for colored range counting in R2 for the case where query ranges are squares. Our structure uses O(n polylog n) storage and has O(polylog n) query time, which is significantly better than what is known for arbitrary rectangular ranges.

The categorical richness problem is related to colored range counting, where the goal is to preprocess a colored point set such that we can efficiently count the number of colors appearing inside a query range. We present a data structure for colored range counting in R2 for the case where query ranges are squares. Our structure uses O(n polylog n) storage and has O(polylog n) query time, which is significantly better than what is known for arbitrary rectangular ranges.

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

Title of host publication | 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2015), November 3-6, 2015, Seattle, Washington, USA |

Place of Publication | New York |

Publisher | Association for Computing Machinery, Inc |

Number of pages | 10 |

ISBN (Print) | 978-1-4503-3967-4 |

DOIs | |

Publication status | Published - 2015 |

Event | 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2015) - Seattle, United States Duration: 3 Nov 2015 → 6 Nov 2015 Conference number: 23 http://sigspatial2015.sigspatial.org/ |

### Conference

Conference | 23rd SIGSPATIAL International Conference on Advances in Geographic Information Systems (ACM SIGSPATIAL 2015) |
---|---|

Abbreviated title | ACM SIGSPATIAL 2015 |

Country | United States |

City | Seattle |

Period | 3/11/15 → 6/11/15 |

Internet address |

## Keywords

- Algorithms for geographic data, raster data sets, patch richness,