Search

In past studies, the digital straight-line segment is defined as a figure approximating the straight-line segment in the continuous space, by grid points in the discrete space. Because of this definition, the properties of the segment vary depending on the approximation process, which prevented the development of a general discussion. For this problem, the authors introduced a topology into the discrete space, and defined the digital straight-line segment using only the topology. As a result, the digital straight-line segment can be defined generally for various spaces and topologies, and the properties of the segment can be analyzed. In this paper, the properties of the digital straight-line segment are analyzed based on the 5-neighborhood concept. As the first step, the assertion that characterizes the digital straight-line segment, as well as five equivalent assertions are presented. Then, it is shown that by using those assertions, the corresponding segment generation algorithm can easily be obtained, and the figure generated by the segment generation algorithm which is known in the CG technology is the same as the proposed digital straight-line segment. © 1998 Scripta Technica. Electron Comm Jpn Pt 3, 81(6): 16–26, 1998 [ABSTRACT FROM AUTHOR]

This paper discusses the problems of finding one of the largest similar substructures in tree Tb to tree Ta, where both Ta and Tb are rooted and ordered trees (RO-trees) or unrooted and cyclically ordered trees (CO-trees). A maximal closest common ancestor mapping and a largest similar substructure in Tb to Ta based on this mapping are defined and two algorithms are proposed for finding one of the largest similar substructures for RO-trees and that for CO-trees. The time and space complexities of the algorithm for RO-trees are OT(NaNb) and OS(NaNb), respectively; and those of the algorithm for CO-trees are OT(mambNaNb) and OS((ma + mb)NaNb), respectively, where ma(mb) and Na(Nb) are the largest degree of a vertex and the number of vertices of Ta(Tb), respectively. © 1997 Scripta Technica, Inc. Electron Comm Jpn Pt 3, 80(2): 92–104, 1997 [ABSTRACT FROM AUTHOR]

Assume that G is an undirected planar graph and the edge length of G is nonnegative real number. When k terminal pairs are specified on two specified face boundaries, this paper gives an algorithm that derives the "noncrossing paths" with the minimum sum of lengths that connects the respective terminal pairs. By the noncrossing paths is meant the paths which do not cross on the plane, although the point or the edge may be shared. The computation time of the proposed algorithm is O(n log n), where n is the number of points on the planar graph G; k need not to be a constant. [ABSTRACT FROM AUTHOR]