期刊
THEORETICAL COMPUTER SCIENCE
卷 319, 期 1-3, 页码 203-227出版社
ELSEVIER
DOI: 10.1016/j.tcs.2004.02.015
关键词
discrete plane; discrete line; connectivity of discrete object; connectivity number
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 Reveilles analytical definition (These d'Etat, Universite Louis Pasteur, Strasbourg, France, 1991). Accordingly, a discrete plane is a set P(a, b, c, mu, omega) of integer points (x, y, z) satisfying the Diophantine inequalities 0 less than or equal to ax + by + cz + mu < omega. The parameter mu is an element of Z estimates the plane intercept while omega is an element of N is the plane thickness. Given three integers (plane coefficients) a, b, and c with 0 less than or equal to a less than or equal to b less than or equal to c, one can seek the value of omega beyond which the discrete plane P(a, b, c, mu, omega) is always connected. We call this remarkable topological invariable the connectivity number of P(a, b, c, mu, omega) and denote it Omega(a, b, c). Despite several attempts over the last 10 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 Omega(a, b, c) and design an O(alogb) algorithm for its computation. (C) 2004 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据