Connectivity of discrete planes

Valentin E. Brimkov, Reneta P. Barneva

February, 2003

Studying connectivity of discrete objects is a major issue in discrete geometry and topology. In the present work we deal with connectivity of discrete planes in the framework of Reveill es analytical definition [11]. Accordingly, a discrete plane is a set P (a, b, c, ,,,,, ) of integer points (x, y, z) satisfying the Diophantine inequalities 0 ax + by + cz + < . The parameter Z estimates the plane intercept while N is the plane thickness. Given three integers (plane coefficients) a, b, and c with 0 a b c, one can seek the maximal for which the discrete plane P (a, b, c, ,,,,, ) is disconnected. We call this remarkable topological invariable the connectivity number of P (a, b, c, ,,,,, ) and denote it (a, b, c). Despite several attempts over the last ten years to determine the connectivity number, this is still an open question. In the present paper we propose a solution to the problem. For this, we first investigate some combinatorial properties of discrete planes. These structural results facilitate the deeper understanding of the discrete plane structure. On this basis, we obtain a series of results, in particular, we provide an explicit solution to the problem under certain conditions. We also obtain exact upper and lower bounds on (a, b, c) and design an O(a log b) algorithm for its computation.

Download: CITR-TR-125.pdf (330 KB)

Back to Technical Report page.

You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45 (forty-five) days from the most recent time that you verified that this technical report is still available from the CITR web site under terms that include this permission. All other rights are reserved by the author(s).

© CITR, The University of Auckland, 2002