### Abstract

Given a fixed distribution of point location queries among the triangles in a triangulation of the plane, a data structure is presented that achieves, within constant multiplicative factors, the entropy bound on the expected point location query time. The data structure is a simple variation of Kirkpatrick's classic planar point location structure [D.G. Kirkpatrick, SIAM J. Comput. 12 (1) (1983) 28-35], and has linear construction costs and space requirements.

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

Pages (from-to) | 19-22 |

Number of pages | 4 |

Journal | Computational Geometry: Theory and Applications |

Volume | 29 |

Issue number | 1 |

DOIs | |

State | Published - Sep 2004 |

### Keywords

- Distribution-sensitive data structures
- Point location

### ASJC Scopus subject areas

- Computer Science Applications
- Geometry and Topology
- Control and Optimization
- Computational Theory and Mathematics
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Expected asymptotically optimal planar point location'. Together they form a unique fingerprint.

## Cite this

Iacono, J. (2004). Expected asymptotically optimal planar point location.

*Computational Geometry: Theory and Applications*,*29*(1), 19-22. https://doi.org/10.1016/j.comgeo.2004.03.010