Area-efficient algorithms for straight-line tree drawings

We investigate several straight-line drawing problems for bounded-degree trees in the integer grid without edge crossings under various types of drawings: (1) upward drawings whose edges are drawn as vertically monotone chains, a sequence of line segments, from a parent to its children, (2) order-preserving drawings which preserve the left-to-right order of the children of each vertex, and (3) orthogonal straight-line drawings in which each edge is represented as a single vertical or horizontal segment.

Main contribution of this paper is a unified framework to reduce the upper bound on area for the straight-line drawing problems from O(nlogn) (Crescenzi et al., 1992) to O(nloglogn). This is the first solution of an open problem stated by Garg et al. (1993). We also show that any binary tree admits a small area drawing satisfying any given aspect ratio in the orthogonal straight-line drawing type.

Our results are briefly summarized as follows. Let T be a bounded-degree tree with n vertices. Firstly, we show that T admits an upward straight-line drawing with area O(nloglogn). If T is binary, we can obtain an O(nloglogn)-area upward orthogonal drawing in which each edge is drawn as a chain of at most two orthogonal segments and which has O(n/logn) bends in total. Secondly, we present O(nloglogn)-area (respectively, -volume) orthogonal straight-line drawing algorithms for binary trees with arbitrary aspect ratios in 2-dimension (respectively, 3-dimension). Finally, we present some experimental results which shows the area requirements, in practice, for (order-preserving) upward drawing are much smaller than theoretical bounds obtained through analysis.     

On the number of guard edges of a polygon

This paper establishes tight bounds on the number of edges of a polygon from which every point in the polygon is visible; we call them guard edges. For a nonstarshaped polygon, there can be at most three guard edges. For a polygon with holes, there may be at most six; three on the outer boundary and three on one of the holes. The results give new insights into the structure of visibility in polygons and shed light on developing an efficient algorithm for finding all guard edges of a polygon with or without holes. This work was partially supported by the Korea Science and Engineering Foundation (Project No. 91-01-01).     

Synchronization of the bidirectionally coupled unified chaotic system via sum of squares method

This paper considers the synchronization problem of the bidirectionally coupled unified chaotic system. Many previous works require the assumption that the states of the system are bounded and their range are known. This assumption may not hold for arbitrary controllers, and thus, it is not suitable to make this assumption beforehand. Accordingly, we propose the novel control method for bidirectionally coupled unified chaotic system via sum of squares method without this assumption. Numerical simulations show the validity and advantage of the proposed method.     

Computing minimum-area rectilinear convex hull and L-shape

We study the problems of computing two non-convex enclosing shapes with the minimum area; the L-shape and the rectilinear convex hull. Given a set of n points in the plane, we find an L-shape enclosing the points or a rectilinear convex hull of the point set with minimum area over all orientations. We show that the minimum enclosing shapes for fixed orientations change combinatorially at most O(n) times while rotating the coordinate system. Based on this, we propose efficient algorithms that compute both shapes with the minimum area over all orientations. The algorithms provide an efficient way of maintaining the set of extremal points, or the staircase, while rotating the coordinate system, and compute both minimum enclosing shapes in O(n²) time and O(n) space. We also show that the time complexity of maintaining the staircase can be improved if we use more space.