We present a quadtree-based decomposition of the interior of a polygon with holes. The complete decomposition yields a constant factor approximation of the minimum weight Steiner triangulation (MWST) of the polygon. We show that this approximate MWST supports ray shooting queries in the query-sensitive sense as defined by Mitchell, Mount and Suri. A proper truncation of our quadtree-based decomposition yields another constant factor approximation of the MWST. For a polygon with n vertices, the complexity of this approximate MWST is O(nlogn) and it can be constructed in O(nlogn) time. The running time is optimal in the algebraic decision tree model.
We consider the following problem. Given a simple polygon P, possibly with holes, and having n vertices, compute a pair of equal radius disks that do not intersect each other, are contained in P, and whose radius is maximized. Our main result is a simple randomized algorithm whose expected running time, on worst case input, is O(nlogn).
In this paper we study greedy in-place sorting algorithms which miraculously happen to work in reasonable time. Dumb-Sort which repeatedly compares all possible pairs of array cells sorts n elements in n-1 cycles, or time O(n3). Not-So-Dumb-Sort, which only tests adjacent cells, also sorts in n-1 cycles, or in time O(n2). Guess-Sort, a randomized version of Dumb-Sort, runs in expected time O(n2logn). And Fun-Sort, an in-place variant of Insertion-Sort that performs repeated insertions by binary search into an initially unsorted array, sorts in time O(n2logn).
Protection of Keys Against Modification Attack
In a recent work, Anderson and Kuhn described an attack against tamper-resistant devices wherein a secret key stored in EEPROM is compromised using a simple and low-cost attack. The attack consists of setting bits in EEPROM using low-cost probes and observing the effect on the output of the device, These attacks are extremely general. as they apply to virtually any cryptosystem. The objective of the present work is to explore cryptographic techniques with the goal of raising the cost (in terms of both time and money) or carrying out the EEPROM attacks by Class I attackers, at least to the point where it is as prohibitive as the cost of purchasing more expensive equipment.
We survey the basic results on regular tree languages over unranked alphabets; that is, we use an unranked alphabet for the labels of nodes, we allow unbounded, yet regular, degree nodes and we treat sequences of trees that, following Courcelle, we call hedges.
The survey was begun by the first and third authors. Subsequently, when they discovered that the second author had already written a summary of this view of tree automata and languages, the three authors decided to join forces and produce a consistent review of the area.
The survey is still unfinished because we have been unable to find the time to finish it. We are making it available in this unfinished form as a research report because it has, already, been heavily cited in the literature.
We introduce a new visual technique for the specification of context in hierarchically structured documents such as those defined by XHTML and XML. The technique is based on a formal graph model called T-graphs and on what we call T-configurations in (abstract) document trees. A T-configuration is a restricted substructure of a tree. The technique is implemented in the current version of DESIGNER. Although we apply this technique to the specification of context-dependent stylesheets for XHTML and XML documents, the technique has much wider applicability. For example, it can be applied to query specification for structured documents and to computer program transformations.
Previously, we introduced a context-specification method that used regular expressions to specify sets of paths in a tree that we called caterpillar expressions. The work on T-graphs is an attempt to provide a 90 percent solution to context-specification problems that solves, in practice, almost all context-specification problems. T-graphs are much easier to visualize and to construct than are caterpillar expressions; they are both a restriction of and a generalization of caterpillar expressions.
We compare T-graphs with the context specification techniques found in other stylesheet systems and we also provide examples of context that we can and cannot specify with T-graphs. Although T-graphs are restrictive, they lend themselves to visual construction and modification, our main requirement when we designed this context-specification method. We also investigate the time and space complexity of T-graph matching, a necessity for efficient implementation.
This is a full and extended version of our conference papers that were presented at DL '99 and at ICCC/EP '99.
We consider a competitive facility location problem with two players. Players alternate placing points, one at a time, into the playing arena, until each of them has placed n points. The arena is then subdivided according to the nearest-neighbor rule, and the player whose points control the larger area wins. We present a winning strategy for the second player, where the arena is a circle or a line segment. We also consider a variation where players can play more than one point at a time for the circle arena.
It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Theta(n2). It is also known that if the points are chosen Independently Identically Distributed uniformly from a 3-dimensional region such as a cube or sphere, then the expected complexity falls to O(n). In this paper we introduce the problem of analyzing what occurs if the points are chosen from a 2-dimensional region in 3-dimensional space. As an example, we examine the situation when the points are drawn from a Poisson distribution on the surface of a convex polytope.
Let P be the boundary of a convex polytope and Sn be a set of points drawn from the 2-dimensional Poisson distribution with rate n over P In a companion paper the authors show that the expected complexity of the 3-dimensional Voronoi Diagram of Sn is O(n). The derivation of that fact used two lemmas describing the geometric structure of the intersection of various types of spheres with P. This note provides the proofs of those two lemmas.
Let P be a set of n points in the plane. We want to find a set S(P,l*) of axis-parallel squares with edge length l* such that each point of P is associated with three squares, each point of P lies on the boundary of its three associated squares, no two squares of S(P,l*) intersect, and l* is maximized. We show how to solve this problem in O(n2 logn) time.
It is well known that the complexity, i.e., the number of vertices, edges and faces, of the 3-dimensional Voronoi diagram of n points can be as bad as Theta(n2). Interest has recently arisen as to what happens, both in deterministic and probabilistic situations, when the three dimensional points are restricted to lie on the surface of a 2-dimensional object. In this paper we consider the situation when the points are drawn from a 2-dimensional Poisson distribution with rate n over a fixed union of triangles in R3. We show that with high probability the complexity of their Voronoi diagram is nearly O(n).
This implies, for example, that the complexity of the Voronoi diagram of points chosen from the surface of a general fixed polyhedron in R3 will also be nearly O(n) with high probability.