Research Reports 1998

HKUST-TCSC-1998-01
Otfried Cheong and René van Oostrum.
Reaching a Polygon with Directional Uncertainty.

Assume a robot that, when directed to move in a particular direction, is guaranteed to move inside a cone of angle alpha centered at the specified direction. The robot has to reach a convex polygonal goal G, while avoiding polygonal obstacles of complexity n. We show that the complexity of the safe region, from where the robot can reach the goal with a single motion with uncertainty alpha, is O(m+n), and can be computed in time O((m+n) log(m+n)), if alpha is assumed constant.

HKUST-TCSC-1998-02
Jürgen Albert, Dora Giammarresi, and Derick Wood.
Extended Context-Free Grammars and Normal Form Algorithms.

We investigate the complexity of a variety of normal-form transformations for extended context-free grammars, where by extended we mean that the set of right-hand sides for each nonterminal in such a grammar is a regular set. The study is motivated by the implementation project GraMa which will provide a C++ toolkit for the symbolic manipulation of context-free objects just as Grail does for regular objects.

Our results generalize known bounds for context-free grammars but do so in nontrivial ways. Specifically, we introduce a new representation scheme for extended context-free grammars (the symbol-threaded expression forest), a new normal form for these grammars (dot normal form) and new regular expression algorithms.

HKUST-TCSC-1998-03
Dora Giammarresi and Derick Wood.
Transition Diagram Systems and Normal Form Algorithms.

We investigate the complexity of a variety of normal-form transformations for transition diagram systems, which are a parsing view of extended context-free grammars. A transition diagram systems is a finite collection of finite-state machines each of which is labeled with a unique nonterminal symbol. The study is motivated by the implementation project GraMa which will provide a C++ toolkit for the symbolic manipulation of context-free objects just as Grail does for regular objects.

HKUST-TCSC-1998-04
Anne Brüggemann-Klein, Stefan Hermann, and Derick Wood.
Context and Caterpillars and Structured Documents.

We present a novel, yet simple, technique for the specification of context in structured documents that we call caterpillar expressions. Although we are applying this technique in the specification of context-dependent style sheets for HTML, XML, and SGML documents, it is clear that it can be used in other environments such as query specification for structured documents and for computer program transformations.

In addition, we present a number of theoretical results that allow us to compare the expressive power of caterpillar expressions to that of tree automata.

HKUST-TCSC-1998-05
Xinxin Wang and Derick Wood.
A Conceptual Model for Tables.

We describe a new, simple conceptual model for tables. The conceptual model treats a table as a map that has a domain which is a product of categories or index sets and a codomain which is a set of entry values. We demonstrate how we can use the model to specify the semantics of some tabular editing operations.

HKUST-TCSC-1998-06
Sven Schuierer and Derick Wood.
Multiple-Guard Kernels of Simple Polygons.

We study a generalization of the kernel of a polygon. A polygon P is k guardable if there are k points in P such that, for all points p in P, there is at least one of the k points that sees p. We call the k points a k-guard set of P and the k-kernel of a polygon P is the union of all k-guard sets of P. The usual definition of the kernel of a polygon is now the one-kernel in this notation.

We show that the two-kernel of a simple polygon P with n edges has O(n4) components and that there are polygons with Omega(n) components. Moreover, we show that the components of the two-kernel of a simple polygon can be paired in a natural manner which implies that the two-kernel of a simple polygon has either one component or an even number of components. Finally, we consider the question of whether there is a non-starshaped simple polygon P such that two-kernel(P) = P. We show that when the two-kernel has only one component, it contains a hole; hence, the two-kernel of a simple polygon P is never P itself. For every k >= 1, there are, however, polygons Pk with holes such that k-kernel(Pk)=Pk.

HKUST-TCSC-1998-07
Eugene Fink and Derick Wood.
Generalized Halfspaces in Restricted-orientation Convexity.

Restricted-orientation convexity, also called O-convexity, is the study of geometric objects whose intersection with lines from some fixed set is empty or connected. The notion of O-convexity generalizes standard convexity and several types of nontraditional convexity.

We introduce O-halfspaces, which are an analog of halfspaces in the theory of O-convexity. We show that this notion generalizes standard halfspaces, explore properties of these generalized halfspaces, and demonstrate their relationship to O-convex sets. We also describe directed O-halfspaces, which are a subclass of O-halfspaces that has some special properties.

We first present some basic properties of O-halfspaces and compare them with the properties of standard halfspaces. We show that O-halfspaces may be disconnected, characterize an O-halfspace in terms of its connected components, and derive the upper bound on the number of components. We then study properties of the boundaries of O-halfspaces. Finally, we describe the complements of O-halfspaces and give a necessary and sufficient condition under which the complement of an O-halfspace is an O-halfspace.

This paper will appear in Journal of Geometry.

HKUST-TCSC-1998-08
Mark de Berg, Otfried Cheong, Olivier Devillers, Marc van Kreveld, and Monique Teillaud.
Computing the Maximum Overlap of Two Convex Polygons Under Translations

Let P be a convex polygon in the plane with n vertices and let Q be a convex polygon with m vertices. We prove that the maximum number of combinatorially distinct placements of Q with respect to P under translations is O(n2+m2+min(nm2+n2m)), and we give an example showing that this bound is tight in the worst case. Second, we present an O((n+m)log(n+m)) algorithm for determining a translation of Q that maximizes the area of overlap of P and Q.

We also prove that the placement of Q that makes the centroids of Q and P coincide realizes an overlap of at least 9/25 of the maximum possible overlap. As an upper bound, we show an example where the overlap in this placement is 4/9 of the maximum possible overlap.

HKUST-TCSC-1998-09
Siu-Wing Cheng and Kam-Hing Lee.

The revised version appears as report HKUST-TCSC-2001-01.

HKUST-TCSC-1998-10
Siu-Wing Cheng, Herbert Edelsbrunner, Ping Fu, and Ka-Po Lam.
Design and Analysis of Planar Shape Deformation.

Shape deformation referes to the continuous change of one geometric object to another. We develop a software tool for planning, analyzing, and visualizing deformations between two shapes in R2. The deformation is generated automatically without any user intervention or specification of feature correspondences. A unique property of the tool is the explicit availability of the two-dimensional shape space, which can be used for designing the deformation either automatically by following constraints and objectives or manually by drawing deformation paths.

HKUST-TCSC-1998-11
Dora Giammarresi, Jean-Luc Ponty and Derick Wood.
Gluskov and Thompson Constructions: A Synthesis.

We reexamine the relationship between the two most popular methods for transforming a regular expression into a finite-state machine: the Glushkov and Thompson constructions. These methods have received more attention recently because of the Standard Generalized Markup Language (SGML) and a revival of interest in symbolic toolkits for regular and context-free expressions, grammars, and machines. We establish that:

In addition, we establish that a number of other inductive constructions yield machines that have their corresponding Glushkov machine hidden in them.

HKUST-TCSC-1998-12
Anne Brüggemann-Klein, Stefan Hermann and Derick Wood.
The Visual Specification of Context.

We introduce a simple and novel visual technique for the specification of context in structured documents called T-graphs that we base on T-configurations in document trees. The technique is implemented in the current version of Designer. Although we are applying this technique in the specification of context-dependent style sheets for HTML, XML and SGML documents, it is clear that it can be used in other environments such as query specification for structured documents and for computer program transformations.

We compare T-graphs with the context specification techniques found in other style-sheet 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.


Web page maintained by Siu-Wing Cheng