Dynamic Ray Shooting and Shortest Paths in Planar Subdivisions via Balanced Geodesic Triangulations

摘要: We give new methods for maintaining a data structure that supports ray-shooting and shortest-path queries in dynamically changing connected planar subdivision S. Our approach is based on dynamic method balanced decomposition of simple polygon via geodesic triangles. maintain such triangulations by viewing their dual trees as trees. show rotations these can be implemented “diagonal swapping” operations performed the corresponding triangles, edge insertion deletion using akin to standardsplitandspliceoperations. also point location triangulation, so we may implement first locating ray's endpoint then walking along ray from triangle until hit boundary some region The shortest path between two points same obtained either following or taking shortcut through common tangent. usesO(n) space updates inO(log2n) worst-case time, wherenis current size It outperforms previous best this problem lognfactor all complexity measures (space, query times, update times).