TY - JOUR

T1 - An efficient algorithm for the 1D total visibility-index problem and its parallelization

AU - Afshani, Peyman

AU - De Berg, Mark

AU - Casanova, Henri

AU - Karsin, Ben

AU - Lambrechts, Colin

AU - Sitchinava, Nodari

AU - Tsirogiannis, Constantinos

PY - 2018/8/1

Y1 - 2018/8/1

N2 - Let T be a terrain and P be a set of points on its surface. An important problem in Geographic Information Science (GIS) is computing the visibility index of a point p on P, that is, the number of points in P that are visible from p. The total visibility-index problem asks for the visibility index of every point in P. We present the first subquadratic-time algorithm to solve the one-dimensional total-visibility-index problem. Our algorithm uses a geometric dualization technique to reduce the problem to a set of instances of the red-blue line segment intersection counting problem, allowing us to find the total visibility-index in O(n log2 n) time. We implement a naive O(n2) approach and four variations of our algorithm: one that uses an existing red-blue line segment intersection counting algorithm and three new approaches that leverage features specific to our problem. Two of our implementations allow for parallel execution, requiringO(log2 n) time and O(n log2 n) work in the CREW PRAM model. We present experimental results for both serial and parallel implementations on synthetic and real-world datasets using two hardware platforms. Results show that all variants of our algorithm outperform the naive approach by several orders of magnitude. Furthermore, we show that our special-case red-blue line segment intersection counting implementations out-perform the existing general-case solution by up to a factor 10. Our fastest parallel implementation is able to process a terrain of more than 100 million vertices in under 3 minutes, achieving up to 85% parallel efficiency using 16 cores.

AB - Let T be a terrain and P be a set of points on its surface. An important problem in Geographic Information Science (GIS) is computing the visibility index of a point p on P, that is, the number of points in P that are visible from p. The total visibility-index problem asks for the visibility index of every point in P. We present the first subquadratic-time algorithm to solve the one-dimensional total-visibility-index problem. Our algorithm uses a geometric dualization technique to reduce the problem to a set of instances of the red-blue line segment intersection counting problem, allowing us to find the total visibility-index in O(n log2 n) time. We implement a naive O(n2) approach and four variations of our algorithm: one that uses an existing red-blue line segment intersection counting algorithm and three new approaches that leverage features specific to our problem. Two of our implementations allow for parallel execution, requiringO(log2 n) time and O(n log2 n) work in the CREW PRAM model. We present experimental results for both serial and parallel implementations on synthetic and real-world datasets using two hardware platforms. Results show that all variants of our algorithm outperform the naive approach by several orders of magnitude. Furthermore, we show that our special-case red-blue line segment intersection counting implementations out-perform the existing general-case solution by up to a factor 10. Our fastest parallel implementation is able to process a terrain of more than 100 million vertices in under 3 minutes, achieving up to 85% parallel efficiency using 16 cores.

KW - Computational geometry

KW - Parallel algorithms

KW - Persistent data structures

KW - Terrain visibility

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

U2 - 10.1145/3209685

DO - 10.1145/3209685

M3 - Journal article

AN - SCOPUS:85052704780

SN - 1084-6654

VL - 23

JO - ACM Journal of Experimental Algorithmics

JF - ACM Journal of Experimental Algorithmics

M1 - 2.3

ER -