2013/12/08 by Natan Rubin, Rubin, Natan
Computer Science · Social Sciences · #Computational Geometry and Mesh Generation #Historical Geography and Cartography #Advanced Vision and Imaging
paper · pdf · doi:10.48550/arxiv.1312.2194
Let P be a collection of n points in the plane, each moving along some\nstraight line at unit speed. We obtain an almost tight upper bound of\nO(n2+\ε), for any \ε>0, on the maximum number of discrete\nchanges that the Delaunay triangulation mathbbDT(P) of P experiences\nduring this motion. Our analysis is cast in a purely topological setting, where\nwe only assume that (i) any four points can be co-circular at most three times,\nand (ii) no triple of points can be collinear more than twice; these\nassumptions hold for unit speed motions.\n