Inverse semigroups determined by their lattices of convex inverse subsemigroups I

Every inverse semigroup possesses a natural partial order and therefore convexity with respect to this order is of interest. We study the extent to which an inverse semigroup is determined by its lattice of convex inverse subsemigroups; that is, if the lattices of two inverse semigroups are isomorphic, how are the semigroups related? We solve this problem completely for semilattices and for inverse semigroups in general reduce it to the case where the lattice isomorphism induces an isomorphism between the semilattices of idempotents of the semigroups. For many inverse semigroups, such as the monogenic ones, this case is the only one that can occur. In Part II, a study of the reduced case enables us to prove that many inverse semigroups, such as the free ones, are strictly determined by their lattices of convex inverse subsemigroups, and to show that the answer obtained here for semilattices can be extended to a broad class of inverse semigroups, including all finite, aperiodic ones. Received September 24, 2002; accepted in final form December 15, 2002.     

Hierarchical Decompositions and Circular Ray Shooting in Simple Polygons

A hierarchical decomposition of a simple polygon is introduced. The hierarchy has logarithmic depth, linear size, and its regions have at most three neighbors. Using this hierarchy, circular ray shooting queries in a simple polygon on n vertices can be answered in O(log² n) query time and O(n log n) space. If the radius of the circle is fixed, the query time can be improved to O(log n) and the space to O(n).     

Spanning Trees Crossing Few Barriers

We consider the problem of finding low-cost spanning trees for sets of $n$ points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a given set of $m$ barriers. We obtain the following results: (i) if the barriers are possibly intersecting line segments, then there is always a spanning tree of cost $O(\min(m^2,m\sqrt{n}))$; (ii) if the barriers are disjoint line segments, then there is always a spanning tree of cost $O(m)$; (iii) ] if the barriers are disjoint convex objects, then there is always a spanning tree of cost $O(n+m)$. All our bounds are worst-case optimal, up to multiplicative constants.     

Texture dependence of capillary instabilities in nematic liquid crystalline fibres

Static and dynamic linear analyses of axisymmetric capillary instabilities in textured nematic liquid crystalline fibres are performed using the equations of nemato-statics and inviscid nemato-dynamics. Three representative textures, viz. axial, onion, and radial, are analysed to show all possible effects of Frank gradient elasticity on the wavelength selection and growth rate of peristaltic modes driven by surface area reduction. It is found that Frank elasticity may tend to stabilize or destabilize the fibre, depending on the initial fibre texture. Axial textures tend to stabilize the fibre through the director splay-bend distortions driven by surface tilting. Onion textures are destabilized by decreasing azimuthal bend elastic energy caused by surface displacement. Radial textures exhibit a stabilizing tilt mechanism due to bend modes and a destabilizing displacement mechanism due to splay modes, but the former is predicted to be dominant. The static analysis provides good estimates of the instability thresholds while the transient energy balance provides information on the fastest growing modes. The static and dynamic results are compared and shown to be fully consistent. The couplings between splay and/or bend distortions, surface tilting, and surface displacement in nematic fibres are characterized and used to explain the deviations from the classical Rayleigh instability.