A finite-state machine is called a Thompson machine if it can be constructed from an empty-free regular expression using the construction of Thompson as modified by Hopcroft and Ullman. We call the underlying digraph of a Thompson machine a Thompson digraph. We characterize Thompson digraphs and we give an algorithm that generates an equivalent regular expression from a Thompson machine that has size linear in the total number of states and transitions. Although the algorithm is simple, it is novel in that the usual constructions of equivalent regular expressions from finite-state machines produce regular expressions that have size exponential in the size of the given machine, in the worst case. The algorithm provides a tentative first step in the construction of small expressions from finite-state machines.
This research was supported under a grant from the Research Grants Council of Hong Kong SAR. It was carried out while the first and second authors were visiting HKUST.
Strong visibility is a generalization of standard visibility, defined with respect to a fixed set of line orientations. We investigate computational properties of this generalized visibility, as well as the related notion of strong convexity, and describe algorithms for the following tasks:
Keywords: Generalized visibility; convexity; restricted orientations.
All too often a seemingly insurmountable divide between theory and practice can be witnessed. In this paper we try to contribute to narrowing this gap in the field of ad-hoc routing. In particular we consider two aspects: We propose a new geometric routing algorithm which is outstandingly efficient on practical average-case networks, however is also in theory asymptotically worst-case optimal. On the other hand, we are able to drop the formerly necessary assumption that the distance between network nodes may not fall below a constant value, an assumption that cannot be maintained for practical networks. Abandoning this assumption we identify from a theoretical point of view two fundamentally different classes of cost metrics for routing in ad-hoc networks.
Delaunay meshes with bounded circumradius to shortest edge length ratio have been proposed in the past for quality meshing. The only poor quality tetrahedra called slivers that can occur in such a mesh can be eliminated by the sliver exudation method. This method has been shown to work for periodic point sets, but not with boundaries. Recently a randomized point-placement strategy has been proposed to remove slivers while conforming to a given boundary. In this paper we present a deterministic algorithm for generating a weighted Delaunay mesh which respects the input boundary and has no poor quality tetrahedron including slivers. As in previous work, we assume that no input angle is acute. This success is achieved by combining the weight pumping method for sliver exudation and the Delaunay refinement method for boundary conformation.
Streaming XML documents has many emerging applications. However, in this paper, we show that the restrictions imposed by data streaming are too restrictive for processing twig queries - the core operation for XML query processing. Previous proposed algorithm TwigStack is an optimal algorithm for processing twig queries with only descendent edges over streams of nodes. The cause of the suboptimality of the TwigStack algorithm is the structurally recursions appearing in XML documents. We show that without relaxing the data streaming model, it is not possible to develop an optimal holistic algorithm for twig queries. Also the computation of the twig queries is not memory bounded. This motivates us to study two variations of the data streaming model: (1) offline sorting is allowed and the algorithm is allowed to select the correct nodes to be streamed and (2) multiple scans on the data streams are allowed. We show the lower bounds of the two variations.
LNCS series: http://www.springer.de/comp/lncs/index.html.
In this note we show that if n lines are chosen at random from R2 then the convex hull of the vertices of the arrangement they form has constant expected size. The random distribution used is that the lines are the duals of n points chosen uniformly and independently from [0,1]2.
We present an algorithm to reconstruct a collection of disjoint smooth closed curves from noisy samples. Our noise model assumes that the samples are obtained by first drawing points on the curves according to a locally uniform distribution followed by a uniform perturbation in the normal directions. Our reconstruction is faithful with probability approaching 1 as the sampling density increases.
Given a set S of n points in Rd, called sites, we consider the problem of approximating the Voronoi cell of a site p by a convex polyhedron with a small number of facets or, equivalently, of finding a small set of approximate Voronoi neighbors of p. More precisely, we define an eps-approximate Voronoi neighborhood of p, denoted AVNeps(p,S), to be a subset of S satisfying the following property: p is an eps-approximate nearest neighbor for any point q inside the convex polyhedron defined by the bisectors between p and the sites in AVNeps(p,S).
We show that there exists a set of eps-approximate Voronoi neighbors with cardinality O(1/sqrt(eps)) for d=2 and cardinality O((1/eps)(d-1)/2log(1/eps)) for any fixed d >= 3. We also provide a worst-case lower bound of Omega((1/eps)(d-1)/2) on the number of approximate Voronoi neighbors. Thus, our bound is tight in the plane and within a factor of O(log(1/eps)) from optimal in dimension d >= 3. Finally, based on our existence proofs, we design efficient algorithms for computing approximate Voronoi neighborhoods.
In this paper we describe the first algorithmic approach to constructing optimal prefix-free codes for infinite sources with geometrically distributed frequencies, e.g., P = {pi (1-p)}i=0infty, 0 < p < 1.
This contrasts with previous work that derived infinite codes by cleverly "guessing" optimal codes for finite sources, validating these guesses by using the sibling property of Huffman encoding, and then showing that the finite codes converge in a very specific sense to an optimal infinite one.
Maximum Residual Energy Path (MREP) routing has been shown an effective routing scheme for energy conservation in battery powered wireless networks. Past studies on MREP routing are based on the assumption that the transmitting node consumes power, but the receiving node does not. This assumption is false if acknowledgement is required as occurs, for example, in some Bluetooth applications.
If the receiving node does not consume power then the MREP routing problem for a single message is easily solvable in polynomial time using a simple Dijkstra-like algorithm. We further show in that when the receiving node does consume power the problem becomes NP-complete and is even impossible to approximate with an exponential approximation factor in polynomial time unless P=NP.