TY - JOUR

T1 - New results on dynamic planar point location

AU - Siu, Wing Cheng

AU - Ravi, Janardan

PY - 1992

Y1 - 1992

N2 - A point location scheme is presented for a dynamic planar subdivision whose underlying graph is only required to be connected. The operations supported include: reporting the name of the region containing a query point, inserting/deleting an edge, and inserting/deleting/moving a degree-2 vertex. The scheme uses O(n) space, has a worst-case query time of O(log2 n), and a worst-case update time of O(log n), where n is the number of vertices currently in the subdivision. Insertion (respectively, deletion) of an arbitrary k-edge chain inside a region can be performed in O(k log(n + k)) (respectively, O(k log n)) time in worst-case. The scheme outperforms the solutions given in works by Fries, Mehlhorn, and Naeher and by Overmars and also handles more general subdivisions than the schemes given in works by Preparata and Tamassia. The result is based on a new solution to a dynamic visibility problem for a set of line segments in the plane that are nonintersecting, except possibly at endpoints. The scheme is then extended to speed up the insertion/deletion of a k-edge monotone chain to O(log2 n log log n + k) time (or O(log n log log n + k) time for an alternative model of input), but at the expense of increasing the other time bounds slightly. Additional results include a generalization to subdivisions consisting of algebraic segments of bounded degree and a persistent scheme that allows point location queries in the past and updates in the present.

AB - A point location scheme is presented for a dynamic planar subdivision whose underlying graph is only required to be connected. The operations supported include: reporting the name of the region containing a query point, inserting/deleting an edge, and inserting/deleting/moving a degree-2 vertex. The scheme uses O(n) space, has a worst-case query time of O(log2 n), and a worst-case update time of O(log n), where n is the number of vertices currently in the subdivision. Insertion (respectively, deletion) of an arbitrary k-edge chain inside a region can be performed in O(k log(n + k)) (respectively, O(k log n)) time in worst-case. The scheme outperforms the solutions given in works by Fries, Mehlhorn, and Naeher and by Overmars and also handles more general subdivisions than the schemes given in works by Preparata and Tamassia. The result is based on a new solution to a dynamic visibility problem for a set of line segments in the plane that are nonintersecting, except possibly at endpoints. The scheme is then extended to speed up the insertion/deletion of a k-edge monotone chain to O(log2 n log log n + k) time (or O(log n log log n + k) time for an alternative model of input), but at the expense of increasing the other time bounds slightly. Additional results include a generalization to subdivisions consisting of algebraic segments of bounded degree and a persistent scheme that allows point location queries in the past and updates in the present.

UR - http://www.scopus.com/inward/record.url?scp=0026929520&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0026929520&partnerID=8YFLogxK

U2 - 10.1137/0221057

DO - 10.1137/0221057

M3 - Article

AN - SCOPUS:0026929520

SN - 0097-5397

VL - 21

SP - 972

EP - 999

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 5

ER -