# Tech Report CS-89-24

## Dynamic Planar Point Location with Optimal Query Time

### Abstract:

We present a new dynamic technique for locating a point in a convex planar subdivision whose {\em n} vertices lie on a fixed set of {\em N} horizontal lines. The supported update operations are insertion/deletion of vertices and edges and (horizontal) translation of vertices. Our method achieves query time $O(\log n + \log N)$, space $O(N + n \log N)$, and insertion/deletion time $O(\log n \log N)$. Hence, for $N = O(n)$, the query time is $O(\log n)$, which is optimal. The proposed technique, based on the {\em trapezoid method}, provides an efficient solution to many significant applications where the most frequent operation is the point location query, while updates are more rarely executed.

(complete text in pdf)
{"ft_lang_label":"__label__en","ft_lang_prob":0.8261879,"math_prob":0.949306,"size":862,"snap":"2021-21-2021-25","text_gpt3_token_len":208,"char_repetition_ratio":0.10489511,"word_repetition_ratio":0.0,"special_character_ratio":0.23897912,"punctuation_ratio":0.094339624,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9894979,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2021-05-13T03:36:17Z\",\"WARC-Record-ID\":\"<urn:uuid:bd16dfea-f3a1-4871-861c-468b20736b29>\",\"Content-Length\":\"9672\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:3e8db969-6a35-4dc6-a3bb-14ec41189363>\",\"WARC-Concurrent-To\":\"<urn:uuid:b39f68b3-e630-4167-b541-36ce348559cd>\",\"WARC-IP-Address\":\"128.148.32.12\",\"WARC-Target-URI\":\"https://cs.brown.edu/research/pubs/techreports/reports/CS-89-24.html\",\"WARC-Payload-Digest\":\"sha1:V33K63UF3T2MO6MEXJJV27ITQEKXFMIN\",\"WARC-Block-Digest\":\"sha1:NF3WZIHCTCO5WJTPFMAKLHNJNRXMRBU7\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2021/CC-MAIN-2021-21/CC-MAIN-2021-21_segments_1620243992721.31_warc_CC-MAIN-20210513014954-20210513044954-00014.warc.gz\"}"}