Institutul de Matematică şi Informatică "Vladimir Andrunachievici"
Universitatea de Stat din MoldovaRO EN
On link diameter of a simple rectilinear polygon
Authors: V. Chepoi, F. Dragan
– 0.16 Mb
Abstract
The rectilinear link distance between two points inside a simple rectilinear polygon P is defined to be the minimum number of edges of a path consisting of axis-parallel segments lying inside P. The link diameter of P is the maximum link distance between two points of P. We present an O(n) time algorithm for computing the link diameter of a simple rectilinear polygon P, where n is the number of vertices of P. This improves the previous O(nlogn) time algorithm.Victor Chepoi, Feodor Dragan
Moldavian University,
A.Mateevici str. 60,
Department of Mathematics and Cybernetics,
Kishinev, 277009, Moldova
E-mail: ,
Moldavian University,
A.Mateevici str. 60,
Department of Mathematics and Cybernetics,
Kishinev, 277009, Moldova
E-mail: ,
Fulltext
Contents
- Distributed operating systems for multiprocessors and networks
- Applied program system for the prognosis of the biological activity of chemical compounds: development and use
- Automatized systems for knowledge acquisition
- On the invariance of the Pareto optimal set
- On link diameter of a simple rectilinear polygon
- A note on two constrained parametric problems on networks
- An Invitation to GAP
- The model of the stochastic generator of the test programs and a method of its analyse
- About Shannon's problem for turing machines