-
Article
Relative Convex Hulls in Semi-Dynamic Arrangements
We present a data structure for maintaining the geodesic hull of a set of points (sites) in the presence of pairwise noncrossing line segments (barriers) that subdivide a bounding box into simply connected faces....
-
Article
One-dimensional staged self-assembly
We introduce the problem of staged self-assembly of one-dimensional nanostructures, which becomes interesting when the elements are labeled (e.g., representing functional units that must be placed at specific loc...
-
Chapter
Constrained Tri-Connected Planar Straight Line Graphs
It is known that for any set V of n ≥ 4 points in the plane, not in convex position, there is a 3-connected planar straight line graph G = (V, E) with at most 2n − 2 edges, and this bound is the best possible. We...
-
Article
Disjoint Compatible Geometric Matchings
We prove that for every set of n pairwise disjoint line segments in the plane in general position, where n is even, there is another set of n segments such that the 2n segments form pairwise disjoint simple polyg...
-
Chapter and Conference Paper
Conflict-Free Graph Orientations with Parity Constraints
It is known that every multigraph with an even number of edges has an even orientation (i.e., all indegrees are even). We study parity constrained graph orientations under additional constraints. We consider two ...
-
Article
Augmenting the Edge Connectivity of Planar Straight Line Graphs to Three
We characterize the planar straight line graphs (Pslgs) that can be augmented to 3-connected and 3-edge-connected Pslgs, respectively. We show that if a Pslg with n vertices can be augmented to a 3-edge-connected...
-
Article
Convex partitions with 2-edge connected dual graphs
It is shown that for every finite set of disjoint convex polygonal obstacles in the plane, with a total of n vertices, the free space around the obstacles can be partitioned into open convex cells whose dual grap...
-
Chapter and Conference Paper
One-Dimensional Staged Self-assembly
We introduce the problem of staged self-assembly of one-dimensional nanostructures, which becomes interesting when the elements are labeled (e.g., representing functional units that must be placed at specific loc...
-
Chapter and Conference Paper
Tri-Edge-Connectivity Augmentation for Planar Straight Line Graphs
It is shown that if a planar straight line graph (Pslg) with n vertices in general position in the plane can be augmented to a 3-edge-connected Pslg, then 2n − 2 new edges are enough for the augmentation. This bo...
-
Chapter and Conference Paper
Convex Partitions with 2-Edge Connected Dual Graphs
It is shown that for every finite set of disjoint convex polygonal obstacles in the plane, with a total of n vertices, the free space around the obstacles can be partitioned into open convex cells whose dual grap...
-
Chapter
Combining Qualitative and Quantitative Temporal Reasoning for Criminal Forensics
The paper presents an application of temporal knowledge representation and reasoning techniques to forensic analysis, especially in answering certain investigative questions relating to time-sensitive informat...
-
Article
Staged self-assembly: nanomanufacture of arbitrary shapes with O(1) glues
We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various constraints and pe...
-
Chapter and Conference Paper
Relative Convex Hulls in Semi-dynamic Subdivisions
We present data structures for maintaining the relative convex hull of a set of points (sites) in the presence of pairwise non-crossing line segments (barriers) that subdivide a bounding box into simply connected...
-
Chapter and Conference Paper
Staged Self-assembly: Nanomanufacture of Arbitrary Shapes with O(1) Glues
We introduce staged self-assembly of Wang tiles, where tiles can be added dynamically in sequence and where intermediate constructions can be stored for later mixing. This model and its various constraints and pe...
