Polyhedral studies for minimum-span graph labelling with integer distance constraints

This paper studies the polytope of the minimum‐span graph labelling problems with integer distance constraints (DC‐MSGL). We first introduce a few classes of new valid inequalities for the DC‐MSGL defined on general graphs and briefly discuss the separation problems of some of these inequalities. These are the initial steps of a branch‐and‐cut algorithm for solving the DC‐MSGL. Following that, we present our polyhedral results on the dimension of the DC‐MSGL polytope, and that some of the inequalities are facet defining, under reasonable conditions, for the polytope of the DC‐MSGL on triangular graphs.     

Average Case Analysis of Bounded Space Bin Packing Algorithms

We consider the one-dimensional bin packing problem and analyze the average case performance of bounded space algorithms. The analysis covers a wide variety of bin packing algorithms including Next-K Fit, K-Bounded Best Fit and Harmonic algorithms, as well as of others. We assume discrete item sizes, an assumption which is true in most real-world applications of bin packing. We present a Markov chains method which is general enough to calculate results for any i.i.d. discrete item size distribution. The paper presents many results heretofore unknown or conjectured from simulation. Some of the results are surprising as they differ considerably from results for continuous distributions.     

The relevant prefixes of coloured Motzkin walks: An average case analysis

In this paper we study some relevant prefixes of coloured Motzkin walks (otherwise called coloured Motzkin words). In these walks, the three kinds of step can have α,β and γ colours, respectively. In particular, when α=β=γ=1 we have the classical Motzkin walks while for α=γ=1 and β=0 we find the well-known Dyck walks. By using the concept of Riordan arrays and probability generating functions we find the average length of the relevant prefix in a walk of length n and the corresponding variance in terms of α,β and γ. This result is interesting from a combinatorial point of view and also provides an average case analysis of algorithms related to the problem of ranking and generating uniformly at random the coloured Motzkin words.     

Within country accuracy of tree crown transparency estimates using the image analysis system CROCO: a case study from Switzerland

We evaluated the accuracy of tree crown transparency estimates made with the image analysis system CROCO compared to visual estimates by field observers in Switzerland. Data from Swiss field training courses in 1998 and 1999 each comprising four sessions were used and the median values of the different observers’ scores were assumed as the true values. First, Swiss reference photographs alone were used to obtain the calibration curves needed to predict crown transparency from the image analysis measure DSO. In this case, the CROCO estimates were biased for many species. Second, data from the first three field training sessions were added to the reference photos to derive the calibration curves. In this second case, CROCO provided unbiased estimates of both years, while the estimates by some of the field teams were significantly different from the true values. The result suggests that CROCO can be used as a more reliable reference to detect observer bias within a country than control observers. We conclude that few reference photographs alone are not sufficient, so additional field data should also be used to estimate crown transparency more accurately using CROCO.     

Optimal Average Case Estimation in Hilbert Norms

In contrast to the worst case approach, the average case setting provides less conservative insight into the quality of estimation algorithms. In this paper we consider two local average case error measures of algorithms based on noisy information, in Hilbert norms in the problem element and information spaces. We define the optimal algorithm and provide formulas for its two local errors, which explicitly exhibit the influence of factors such as information, information (measurement) errors, norms in the considered spaces, a subset where approximations are allowed, and “unmodeled dynamics.” Based on the error expression, we formulate in algebraic language the problem of selecting the optimal approximating subspace. The solution is given along with the specific formula for the error, which depends on the eigenvalues of a certain matrix defined by information and norms under consideration. Date received: November 25, 1999. Date revised: May 30, 2000.     

Real-time map labelling for mobile applications

It is essential to label roads, landmarks, and other important features on maps for mobile applications to help users to understand their location and the environment. This paper aims to examine real-time map labelling methods suitable for the small screen on mobile devices. A slider method with a continuous search space was proposed to sequentially label both line and point features. The method starts with defining a range box for possible locations of the label. Then a search is performed, and the range box is reduced, if there are any cartographic objects that overlap the range box. Finally, the label is placed, at the best possible position in the reduced range box according to normal cartographic preferences, where it does not obscure any cartographic object. We implemented this method in a Java environment using the open source library JTS Topology Suite. A case study showed sound cartographic results of the labelling and acceptable computational efficiency.     

Linear time algorithms for an image labelling machine

Region labelling is one of the essential preprocessing operations in an image understanding system. In this paper we present two region labelling algorithms for a multiprocessor architecture with a time complexity of O(n).     

Bisection approach for pixel labelling problem

This paper formulates pixel labelling as a series of two-category classification. Unlike existing techniques, which assign a determinate label to each pixel, we assign a label set to each pixel and shrink the label set step by step. Determinate labelling is achieved within log₂n (n is size of label set) steps. In each step, we bisect the label set into two subsets and discard the one with higher cost of assigning it to the pixel. Simultaneous labelling of an image is carried out by minimizing an energy function that can be minimized via graph cut algorithm. Based on the bisection approach, we propose a bitwise algorithm for pixel labelling, which set one bit of each pixel's label in each step. We apply the proposed algorithm to stereo matching and image restoration. Experimental results demonstrate that both good performance and high efficiency are achieved.     

TAPON-MT: A versatile framework for semantic labelling

Semantic labelling refers to the problem of assigning known labels to the elements of structured information from a source such as an HTML table or an RDF dump with unknown semantics. In the recent years it has become progressively more relevant due to the growth of available structured information in the Web of data that need to be labelled in order to integrate it in data systems. The existing approaches for semantic labelling have several drawbacks that make them unappealing if not impossible to use in certain scenarios: not accepting nested structures as input, being unable to label structural elements, not being customisable, requiring groups of instances when labelling, requiring matching instances to named entities in a knowledge base, not detecting numeric data, or not supporting complex features. In this article, we propose TAPON-MT, a framework for machine learning semantic labelling. Our framework does not have the former limitations, which makes it domain-independent and customisable. We have implemented it with a graphical interface that eases the creation and analysis of models, and we offer a web service API for their application. We have also validated it with a subset of the National Science Foundation awards dataset, and our conclusion is that TAPON-MT creates models to label information that are effective and efficient in practice.     

Average curve of n smooth planar curves

We define the Average Curve (AC) of a compatible set of two or more smooth and planar, Jordan curves. It is independent of their order and representation. We compare two variants: the valley AC (vAC), defined in terms of the valley of the field that sums the squared distances to the input curves, and the zero AC (zAC), defined as the zero set of the field that sums the signed distances to the input curves. Our formulation provides an orthogonal projection homeomorphism from the AC to each input curve. We use it to define compatibility. We propose a fast tracing algorithm for computing a polygonal approximation (PAC) of the AC and for testing compatibility. We provide a linear-cost implementation for tracing the PAC of polygonal approximations of smooth input curves. We also define the inflation of the AC and use it to visualize the local variability in the set of input curves. We argue that the AC and its inflation form a natural extension of the Medial Axis Transform to an arbitrary number of curves. We propose extensions to open curves and to weighted averages of curves, which can be used to design animations.     

An analytic approach to the height of binary search trees

By using analytic tools it is shown that the expected value of the heightH _n of binary search trees of sizen is asymptotically given by EH _n =c logn+ (log logn) and its variance by VH _n = ((log logn)²), wherec=4.31107 …. The same bounds have been obtained by Devroye and Reed [3] by completely different methods. Dedicated to Philippe Flajolet on the occasion of his 50th birthday This research was supported by the Austrian Science Foundation FWF, Grant P10187-MAT. Online publication September 22, 2000.     

Handwritten character recognition by parallel labelling and shape analysis

This paper introduces a shape analysis method for handwritten characters based on polygonal approximation and a recognition on the basis of parallel fuzzy labelling. At first the input character is preprocessed for pixel definition, thinning, and tail-removal, and finally it is fed into the feature extraction and character recognition stages.     

Fault tree analysis with fuzzy gates

Fault tree analysis is an important tool analyzing system reliability. Fault trees consist of gates and events. Gates mean relationships between events. In fault tree analysis, AND, OR gates have been used as typical gates but it is often difficult to model the system structure with the two gates because in many cases we have not exact knowledge on system failure mechanism in early design stage. In this paper, we apply the fuzzy sets theory to modeling the fuzzy system structure, propose the new procedure to calculate the system reliability and a new importance index of basic events.     

The problem of reasoning by case analysis

This article is the twenty-ninth of a series of articles discussing various open research problems in automated reasoning. The problem proposed for research asks one to find criteria that an automated reasoning program can apply to decide when to conduct a case analysis argument and to decide which cases are appropriate. When the choice of employing a case analysis argument is wise and the cases are well chosen, the likelihood that the reasoning program — or, for that matter, a person — will find an answer to the given question is sharply increased.This work was supported by the Office of Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38.     

Average-Case Analysis for a Simple Compression Algorithm

In this paper we treat the static dictionary problem , very well known in computer science. It consists in storing a set S of m elements in the range [1 . . . n ] so that membership queries on S 's elements can be handled in O(1) time. It can be approached as a table compression problem in which a size n table has m ones and the other elements are zeros. We focus our attention on sparse case (m n ). We use a simple algorithm to solve the problem and make an average-case analysis of the total space required when the input derives from uniform probability distribution. We also find some conditions able to minimize storage requirements. We then propose and analyze a new algorithm able to reduce storage requirements drastically to O(m ^4/3 ) . Received December 1, 1997; revised March 1, 1998.     

Boundary matching algorithm for connected component labelling using linear quadtrees

A computationally fast top-down recursive algorithm for connected component labelling using linear quadtrees is presented. The input data structure used is a linear quadtree representing only black leaf nodes. The boundary matching approach used ensures that at most two adjacencies of any black leaf node are considered. Neighbour searching is carried out within restricted subsets of the input quadtree. The time and space complexities of the algorithm are O(Bn) and O(B) respectively for a linear quadtree with B black leaves constructed from a binary array of size 2ⁿ × 2ⁿ. Simulations show the algorithm to be twice as fast as an existing algorithm that uses an identical input data structure. The top-down algorithm presented can also be used to efficiently generate a linear quadtree representing all nodes — ‘grey’, ‘black’ and ‘white’ — in preorder when given an input linear quadtree representing only ‘black’ leaf nodes. The boundary matching algorithm is computationally fast and has low static and dynamic storage costs, making it useful for applications where linear quadtrees are held in main memory.