Portal de Periódicos da CAPES

Computing the shortest watchtower of a polyhedral terrain in O(nlogn) time

1997; Elsevier BV; Volume: 8; Issue: 4 Linguagem: Inglês

10.1016/s0925-7721(96)00009-0

1879-081X

Binhai Zhu,

Advanced Graph Theory Research

Given a polyhedral terrain S with n vertices, the shortest watchtower is defined as the shortest vertical line segment uv whose lower endpoint u lies on S and whose upper endpoint v can see the entire terrain. In 1988 Sharir gave an O(nlog2n) time algorithm for computing the shortest watchtower and posed the open problem of computing the shortest watchtower in O(nlogn) time. In this paper, we show that by extending Dobkin-Kirkpatrick's hierarchical representation of a convex polyhedron, the problem can be solved in O(nlogn) time. This settles the above open problem posed by Sharir. We also discuss the closely related problem of computing the shortest vertical distance between two convex polyhedra.