We consider cameras whose outputs do not reflect true scenes as faulty cameras. To build a fault detection video surveillance system without using additional hardware devices, we use the video outputs from cameras to do self-checking. We study two categories of faults: spatial faults and temporal faults, and reduce the two sub-problems into graph theoretical problems on two graphs (surveillance sharing graph (SSG) and surveillance partitioning graph (SPG)). We prove a theoretical upper bound for the spatial fault detection, and develop two algorithms for detecting the two types of faults respectively.Then, we integrate both in a framework, which is capable of the following: given the outputs from a video surveillance system, it isolates cameras which are faulty or suspected to be faulty. It gives warnings with types of faults, locations, detection confidence. Our experiments confirm the effectiveness of the framework's methodologies.

This video illustrates the k-LinkSolver software for computing k-link shortest paths in weighted regions. The k-LinkSolver implements methods to find paths of length at most (1+e) times the length of a shortest k-link path, for any fixed e>0, and having at most 2k−1 links. The methods implemented are an improvement over the previously known (1+e)-approximation algorithms, which guarantee at most 5k−2 links.

Given a polyhedral terrain T with n vertices, the two-watchtower problem for T calls for finding two vertical segments, called watchtowers, of smallest common height, whose bottom endpoints (bases) lie on T, and whose top endpoints guard T, in the sense that each point on T is visible from at least one of them. In this paper we present the following results for the two-watchtower problem in R2 and R3: (1) We show that the discrete two-watchtowers problem in R2, where the bases are constrained to lie at vertices of T, can be solved in O(n2 log4n) time, significantly improving previous solutions. The algorithm works, without increasing its asymptotic running time, even if, one of the towers is allowed to be placed anywhere on T. (2) We show that the continuous two-watchtower problem in R2, where the bases can lie anywhere on T, can be solved in O(n3α(n)log3n) time, again significantly improving previous results. (3) Still in R2, we show that the continuous version of the problem of guarding a finite set P ⊂ T of m points by two watchtowers of smallest height can be solved in O(mn log4n) time. (4) The discrete version of the two-watchtower problem in R3 can be solved in O(n11/3 polylog(n)) time; this is the first nontrivial result for this problem in R3.

Early studies of random versus partition testing used the probability of detecting at least one failure as a measure of test effectiveness and indicated that partition testing is not significantly more effective than random testing. More recent studies have focused on proportional partition testing because a proportional allocation of the test cases (according to the probabilities of the subdomains) can guarantee that partition testing will perform at least as well as random testing. We show that this goal for partition testing is not a worthwhile one. Guaranteeing that partition testing has at least as high a probability of detecting a failure comes at the expense of decreasing its relative advantage over random testing. We then discuss other problems with previous studies and show that failure to include important factors (cost, relative effectiveness) can lead to misleading results.

There have been many comparisons of random and partition testing. Proportional partition testing has been suggested as the optimum way to perform partition testing. In this paper we show that this might not be so and discuss some of the problems with previous studies. We look at the expected cost of failures as a way to evaluate the effectiveness of testing strategies and use it to compare random testing, uniform partition testing and proportional partition testing. Also, we introduce partition testing strategies that try to take the cost of failures into account and present some results on their effectiveness.

Studies have shown that random testing can be an effective testing strategy. One of the goals of testing is to estimate the reliability of the program from the test outcomes. The authors extend the Thayer-Lipow-Nelson reliability model (R. Thayer et al., 1978) to account for the cost of errors. They also compare random testing with partition testing by examining upper confidence bounds for the cost weighted performance of the two strategies.>

Random testing is receiving increasing attention in recent years. Aside from its relative simplicity and low cost, studies have shown that random testing is an effective testing strategy. An advantage of random testing is that the reliability of the program can be estimated from the test outcomes. The authors extend the Thayer-Lipow-Nelson reliability model to account for the cost of errors. They also compare random with partition testing by looking at upper confidence bounds for the cost weighted performance of the two strategies.>

We consider the terrain navigation problem in a two-dimensional polygonal subdivision with three types of regions: obstacles, “free” regions (in which one can travel at no cost), and regions in which cost is proportional to distance traveled. We present an algorithm whose running time is O(E + nlog n), where n is the number of vertices representing the subdivision, and E is bounded above by the size of the visibility graph induced by the set of obstacles and free regions, which is no worse than quadratic (O(n2)). In addition, we present algorithms to solve a variety of important generalizations and applications: (1) an O(n2) algorithm for constructing a critical graph of size O(n2) (which can be searched in time O(n2log n) for shortest paths) for the case in which linear features (roads) are added, thereby allowing arbitrary weights on the edges of the subdivision; (2) similar time bounds for the case in which the linear features include a possible “cost of crossing”; (3) an O(n2W) algorithm for finding lexicographically shortest paths in weighted regions (with W different weights); (4) an O(k2n2) algorithm for planning least-risk paths in a simple polygon that contains k line-of-sight threats (this becomes O(k4n4) in polygons with holes); and (5) an O(k2n3) algorithm for finding least-risk watchman routes in simple rectilinear polygons (a watchman route is such that each point in the polygon is visible from at least one point along the route). INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.

Consideration is given to the problem of finding a shortest path between two points in 3-D space with a restricted class of polyhedral obstacles (vertical buildings with a fixed number k of distinct heights). For the case when all the obstacles have equal heights, a shortest-path algorithm is presented with complexity O(n/sup 2/), i.e. the same complexity as for the 2-D case (n is the total number of corners in all the obstacles). For the general case (k distinct heights), an algorithm is presented for finding a shortest path in time O(n/sup 6k-1/). Also presented is an O(n/sup 2/) approximation algorithm that finds paths that are, at most, 8% longer than the shortest path for the case of k distinct heights when certain minimum separation requirements are satisfied, and a description is given of how the approximation algorithm can be extended to the general case (arbitrary separations).>

We consider the terrain navigation problem in a two-dimensional polygonal subdivision consisting of obstacles, “free” regions (in which one can travel at no cost), and regions in which cost is proportional to distance traveled. This problem is a special case of the weighted region problem and is a generalization of the well-known planar shortest path problem in the presence of obstacles. We present an Ο(n2) exact algorithm for this problem and faster algorithms for the cases of convex free regions and/or obstacles. We generalize our algorithm to allow arbitrary weights on the edges of the subdivision. In addition, we present algorithms to solve a variety of important applications: (1) an Ο(n2W) algorithm for finding lexicographically shortest paths in weighted regions (with W different weights); (2) an Ο(k2n2) algorithm for planning least-risk paths in a simple polygon that contains k line-of-sight threats (this becomes Ο(k4n4) in polygons with holes); and (3) an Ο(k2n3) algorithm for finding least-risk watchman routes in simple rectilinear polygons (a watchman route is such that each point in the polygon is visible from at least one point along the route).

Several structural testing strategies are compared in terms of their relative coverage of the program's structure and also in terms of the number of test cases needed to satisfy each strategy. Some of the deficiencies of such comparisons are discussed.>

In this paper we consider the problem of finding shortest routes from which every point in a given space is visible (watchman routes). We show that the problem is NP-hard when the space is a polygon with holes even if the polygon and the holes are convex or rectilinear. The problem remains NP-hard for simple polyhedra. We present O(n) and O(nlogn) algorithms to find a shortest route in a simple rectilinear monotone polygon and a simple rectilinear polygon respectively, where n is the number of vertices in the polygon. Finding optimum watchman routes in simple polygons is closely related to the problem of finding shortest routes that visit a set of convex polygons in the plane in the presence of obstacles. We show that finding a shortest route that visits a set of convex polygons is NP-hard even when there are no obstacles. We present an O(logn) algorithm to find the shortest route that visits a point and two convex polygons, where n is the total number of vertices.

Random testing of programs has usually (but not always) been viewed as a worst case of program testing. Testing strategies that take into account the program structure are generally preferred. Path testing is an often proposed ideal for structural testing. Path testing is treated here as an instance of partition testing, where by partition testing is meant any testing scheme which forces execution of at least one test case from each subset of a partition of the input domain. Simulation results are presented which suggest that random testing may often be more cost effective than partition testing schemes. Also, results of actual random testing experiments are presented which confirm the viability of random testing as a useful validation tool.

In this paper we introduce two classes of program testing strategies that consist of specifying a set of required elements for the program and then covering those elements with appropriate test inputs. In general, a required element has a structural and a functional component and is covered by a test case if the test case causes the features specified in the structural component to be executed under the conditions specified in the functional component. Data flow analysis is used to specify the structural component and data flow interactions are used as a basis for developing the functional component. The strategies are illustrated with examples and some experimental evaluations of their effectiveness are presented.

Certain graph theoretic problems dealing with the testing of structured programs are treated. A structured digraph is a digraph that represents a structured program. A labelling procedure which characterizes structured digraphs is described. An efficient algorithm for finding a minimum path cover for the vertices of digraphs that belong to an important family of structured digraphs is given. To model interactions among code segments the notions of `required pairs' and `must pairs' are introduced and the corresponding constrained path cover problems are shown to be NP-complete even for acyclic structured digraphs.

It is shown that the problem of finding a codeword with least weight and whose weight is not a multiple ofkin a binary linear code belongs to the class of "nondeterministic polynomial (NP)-hard" problems for anyk\geq 2. Some other related problems are shown to belong to the same class. These results were motivated by a conjecture due to Berlekamp, McEliece, and van Tilborg that the problem of finding the Hamming distance of a code is NP-hard.

In this paper various path cover problems, arising in program testing, are discussed. Dilworth's theorem for acyclic digraphs is generalized. Two methods for fmding a minimum set of paths (minimum path cover) that covers the vertices (or the edges) of a digraph are given. To model interactions among code segments, the notions of required pairs and required paths are introduced. It is shown that rmding a minimum path cover for a set of required pairs is NP-hard. An efficient algorithm is given for findng a minimum path cover for a set of required paths. Other constrained path problems are contsidered and their complexities are discussed.