An efficient algorithm for the 1D total Visibility-Index problem

摘要: Let T be a terrain, and let P set of points (locations) on its surface. An important problem in Geographic Information Science (GIS) is computing the visibility index point p P, that is, number are visible from p. The total visibility-index asks for every P. Most applications this involve 2-dimensional terrains represented by grid n square cells, where each cell associated with an elevation value, consists center-points these cells. Current approaches visibility- such terrain take at least quadratic time respect to While nding subquadratic solution 2D open problem, surprisingly, no has been proposed one-dimensional (1D) version problem; 1D x-monotone polyline, polyline vertices. We present O(n log2 n) algorithm solves RAM model. Our based geometric dual- ization technique, which reduces into instances red-blue line segment intersection counting problem. also parallel algorithm, requires O(log2 work CREW PRAM im- plement naive O(n2) approach three variations our algorithm: one employing existing two new ap- proaches perform leveraging features specic MADALGO, Aarhus University, Denmark, fpeyman,constantg@madalgo.au.dk yDepartment Mathematics Computer Science, TU Eindhoven, Netherlands, fmdberg,c.lambrechtsg@tue.nl zDepartment Sciences, University Hawaii Manoa, USA, fhenric,karsin,nodarig@hawaii.edu. last authors were partially supported National Foundation under Grant No. 1533823. experimental results both serial imple- mentations large synthetic real-world datasets, using distinct hardware platforms. Results show all variants outperform several orders magnitude datasets. Furthermore, we inter- section implementations achieve more than 8 times speedup over algorithm. implementation able process 224 vertices 1 minute 16 cores, achieving 7 execution.