### Abstract

A data structure is presented for point location in convex planar subdivisions when the distribution of queries is known in advance. The data structure has an expected query time that differs from the optimal one by only lower order terms in the linear comparison tree model.

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

Title of host publication | Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms |

Pages | 912-921 |

Number of pages | 10 |

State | Published - 2008 |

Event | 19th Annual ACM-SIAM Symposium on Discrete Algorithms - San Francisco, CA, United States Duration: Jan 20 2008 → Jan 22 2008 |

### Publication series

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

### Other

Other | 19th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

Country | United States |

City | San Francisco, CA |

Period | 1/20/08 → 1/22/08 |

### ASJC Scopus subject areas

- Software
- Mathematics(all)

## Fingerprint Dive into the research topics of 'Distribution-sensitive point location in convex subdivisions'. Together they form a unique fingerprint.

## Cite this

Collette, S., Dujmović, V., Iacono, J., Langerman, S., & Morin, P. (2008). Distribution-sensitive point location in convex subdivisions. In

*Proceedings of the 19th Annual ACM-SIAM Symposium on Discrete Algorithms*(pp. 912-921). (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).