We propose an algorithm to compute a conforming Delaunay mesh of a bounded domain specified by a piecewise linear complex. Arbitrarily small input angles are allowed, and the input complex is not required to be a manifold. Our algorithm encloses the input edges with a small buffer zone, a union of balls whose sizes are proportional to the local feature sizes at their centers. In the output mesh, the radius-edge ratio of the tetrahedra outside the buffer zone is bounded by a constant independent of the domain, while that of the tetrahedra inside the buffer zone is bounded by a constant depending on the smallest input angle. Furthermore, the output mesh is graded. Our work is the first that provides quality guarantees for Delaunay meshes in the presence of small input angles.
It has long been known that the number of spanning trees in n node circulant graphs with fixed jumps satisfies a bounded order, constant coefficient, recurrence relation in n. The proof of this fact was algebraic (evaluating products of eigenvalues of the graphs' adjacency matrices) and not combinatorial. In this paper we derive a straightforward combinatorial proof. Instead of trying to decompose a large circulant graph into smaller ones, our technique is to instead work on step-graphs, the unhooked version of circulant graphs, construct a system of linear recurrence relations on the number of different types of forests in the step graph, and then express the number of spanning trees of the circulant graph in terms of the number of different types of forests of the step-graph. This technique is very general and, unlike the algebraic methods previously employed, can also be used to enumerate other parameters of circulant graphs. We illustrate this by using it to prove that the number of Hamiltonian Cycles in a fixed-jump circulant graph also satisfies a bounded order, constant coefficient, recurrence relation in n.
The standard dynamic programming solution to finding k-medians on a line with n nodes requires O(k n2) time. Dynamic programming speed-up techniques, e.g., use of the quadrangle inequality or properties of totally monotone matrices, can reduce this to O(k n) time. However, these speed-up techniques are inherently static and cannot be used in an online setting, i.e., if we want to increase the size of the problem by one new point. Then, in the worst case, we could do no better than recalculating the solution to the entire problem from scratch in O(k n) time. The major result of this paper is to show that we can maintain the dynamic programming speedup in an online setting where points are added from left to right on a line. Computing the new k-medians after adding a new point takes only O(k) amortized time and O(k logn) worst case time (simultaneously). Using similar techniques, we can also solve the online k-coverage with uniform coverage on a line problem with the same time bounds
We present an algorithm to compute a Delaunay mesh conforming to a polyhedron possibly with small input angles. The radius-edge ratio of most output tetrahedra are bounded by a constant, except possibly those that are provably close to small angles. Furthermore, the mesh is not unnecessarily dense in the sense that the edge lengths are at least a constant fraction of the local feature sizes at the edge endpoints. This algorithm is simple to implement as it eliminates most of the computation of local feature sizes and explicit protective zones. Our experimental results validate that few skinny tetrahedra remain and they lie close to small acute inputs.
We study the problem of reconstructing a closed smooth surface S in R3 from n noisy samples. We present a deterministic model of noisy samples. We justify it by proving that the model is satisfied with high probability, if we randomly perturb dense uniform samples on S in the normal directions. Let 0 < gamma <= 1/8 be a constant parameter chosen in advance. We develop an O(n2+gamma)-time algorithm to construct a triangulated surface based on the deterministic model. As n -> infty, the output surface is homeomorphic to S and its approximation error converges to zero.
Casting is a manufacturing process in which liquid is poured into a cast (mould) that has a cavity with the shape of the object to be manufactured. The liquid then hardens, after which the cast is removed. We address geometric problems concerning the removal of the cast. A cast consists of two parts, one of which retracts in a given direction carrying the object with it. Afterwards, the object will be ejected from the retracted cast part. In this paper, we give necessary and sufficient conditions to test the feasibility of the cast part retraction and object ejection, where retraction and ejection directions need not be the same. For polyhedral objects, we show that the test can be performed in O(n2log2 n) time and the cast parts can be constructed within the same time bound. The complexity of the cast parts constructed is worst-case optimal. We also give a polynomial time algorithm for finding a feasible pair of retraction and ejection directions for a given polyhedral object.
The structure of optimal (minimum-cost) prefix-free codes for geometrically distributed sources was first derived by Gallager & Van Voorhis. Their approach was later extended by Merhav, Seroussi and Weinberger to derive optimal codes for "two-sided" geometric distributions. The technique used combines (i) guessing optimal codes and then (ii) validating them using the Huffman encoding algorithms.
This paper presents the first algorithmic approach for constructing optimal prefix-free codes for (infinite) geometrically distributed sources. This approach will work for even more complicated generalizations of geometric sources where solutions cannot be guessed as well as in extensions of Huffman-coding for which the Huffman algorithm no longer works, e.g., non-uniform cost encoding alphabet characters.
The basis of this new approach is a combinatorial derivation of the cyclic properties of optimal codes for infinite geometric (like) sources. This will permit designing efficient algorithms that restrict themselves to searching among codes possessing these properties.
We explore expression automata with respect to determinism, minimization and primeness. We define determinism of expression automata using prefix-freeness. This approach is, to some extent, similar to that of Giammarresi and Montalbano's definition of deterministic generalized automata. We prove that deterministic expression automata languages are a proper subfamily of the regular languages. We define the minimization of deterministic expression automata. Lastly, we discuss prime prefix-free regular languages.
Note that we have omitted almost all proofs in this preliminary version
Point location is the problem of preprocessing a planar polygonal subdivision S of size n into a data structure in order to determine efficiently the cell of the subdivision that contains a given query point. We consider this problem from the perspective of expected query time. We are given the probabilities pz that the query point lies within each cell z in S. The entropy H of the resulting discrete probability distribution is the dominant term in the lower bound on the expected-case query time. We show that it is possible to achieve query time H + O(sqrt(H)+1) with space O(n), which is optimal up to lower order terms in the query time. We extend this result to subdivisions with convex cells, assuming a uniform query distribution within each cell. In order to achieve space efficiency, we introduce the concept of entropy-preserving cuttings.
Given a planar polygonal subdivision S, point location involves preprocessing this subdivision into a data structure so that given any query point q, the cell of the subdivision containing q can be determined efficiently. Suppose that for each cell z in the subdivision, the probability pz that a query point lies within this cell is also given. The goal is to design the data structure to minimize the average search time. This problem has been considered before, but existing data structures are all quite complicated. It has long been known that the entropy H of the probability distribution is the dominant term in the lower bound on the average-case search time. In this paper, we show that a very simple modification of a well-known randomized incremental algorithm can be applied to produce a data structure of expected linear size that can answer point-location queries in O(H) average time. We also present empirical evidence for the practical efficiency of this approach.