A sequential algorithm is presented for computing the exact Euclidean distance transform (DT) of a k-dimensional binary image in time linear in the total number of voxels N. The algorithm, which is based on dimensionality reduction and partial Voronoi diagram construction, can be used for computing the DT for a wide class of distance functions, including the L/sub p/ and chamfer metrics. At each dimension level, the DT is computed by constructing the intersection of the Voronoi diagram whose sites are the feature voxels with each row of the image. This construction is performed efficiently by using the DT in the next lower dimension. The correctness and linear time complexity are demonstrated analytically and verified experimentally. The algorithm may be of practical value since it is relatively simple and easy to implement and it is relatively fast (not only does it run in O(N) time but the time constant is small). A simple modification of the algorithm computes the weighted Euclidean DT, which is useful for images with anisotropic voxel dimensions. A parallel version of the algorithm runs in O(N/p) time with p processors.

(MATH) We show the following:

We investigate the query complexity of exact learning in the membership and (proper) equivalence query model. We give a complete characterization of concept classes that are learnable with a polynomial number of polynomial sized queries in this model. We give applications of this characterization, including results on learning a natural subclass of DNF formulas, and on learning with membership queries alone. Query complexity has previously been used to prove lower bounds on the time complexity of exact learning. We show a new relationship between query complexity and time complexity in exact learning: If any “honest” class is exactly and properly learnable with polynomial query complexity, but not learnable in polynomial time, then P = NP. In particular, we show that an honest class is exactly polynomial-query learnable if and only if it is learnable using an oracle for Γ p 4 .

Prior research has extended the classical PMC (or Symmetric Invalidation) Model to incorporate a priori weights or probabilities associated with units. We consider a similar extension to the BGM (or Asymmetric Invalidation) Model. In contrast to the PMC model, where deciding the weighted diagnosability number is co-NP complete, we show that the diagnosability number in the weighted BGM model can be obtained in O(m/sup 2/) time, where m is the number of tests in the system. We also show that diagnosis in this weighted model can be performed in O(T(n)) time, where n is the number of units in the system and T(n)/spl ap/n/sup 2.376/ is the amount of time needed to multiply two n by n matrices.

We investigate the query complexity of exact learning in the membership and (proper) equivalence query model.We give '

Bshouty, Goldman, Hancock and Matar have shown that up to log n-term DNF formulas can be properly learned in the exact model with equivalence and membership queries. Given standard complexity-theoretical assumptions, we show that this positive result for proper learning cannot be significantly improved in the exact model or the PAC model extended to allow membership queries. Our negative results are derived from two general techniques for proving such results in the exact model and the extended PAC model. As a further application of these techniques, we consider read-thrice DNF formulas. Here we improve on Aizenstein, Hellerstein, and Pitt's negative result for proper learning in the exact model in two ways. First, we show that their assumption of NP ≠ co-NP can be replaced with the weaker assumption of P ≠ NP. Second, we show that read-thrice DNF formulas are not properly learnable in the extended PAC model, assuming RP ≠ NP.

We show that the class of p-branching programs can be exactly learned in ()(rz5) time us:n$ only O(n) equivalence queries and O(n ) membership queries, but neither type of query alone is sufficient for polynomial time learning.

R. Gupta and I.V. Ramakrishnan (1987) proposed a general model for fault diagnosis that uniformly handles intermittent faults, masking, and partial testing. In this model, the diagnosability problem is open if asymmetric invalidation is used, although a polynomial time algorithm was once incorrectly claimed. It is shown that the problem is really co-NP complete. An efficient diagnosis algorithm for this model is presented.>

The concepts of the PMC and BGM self-diagnosing system models of F. P. Preparata et al. (1967) and F. Barsi et al. (1976), respectively, including the notions of fault sets, consistency, and diagnosability number, are reviewed. Two one-step diagnosability algorithms are applied, one to the PMC model and the other to the BGM model. In both models, one-step diagnosability refers to a system's ability to determine all the faulty units from single collection of test results. Using the letters n, m, and tau to denote the number of units, the number of tests, and the diagnosability number, respectively, it is shown that in the BGM model the algorithm has a complexity of O(n tau /sup 2//log tau ), and, in the PMC model, the algorithm has a complexity of O(n tau /sup 2.5/).>

F.P. Preparata et al. (1967) introduced a graph-theoretical model for fault diagnosis called the PMC model. The question of determining the sequential diagnosability number of a system in the PMC model has remained open. The authors formalize the notion of sequential diagnosability. The question of determining the sequential diagnosability number of a system is addressed by showing that the appropriate decision problem is co-NP complete. The problem is also shown to be co-NP complete even when restricted to planar graphs both in the weighted and the BGM models.>