A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk

We propose a very simple ray-shooting algorithm, whose only data structure is a triangulation. The query algorithm, after locating the triangle containing the origin of the ray, walks along the ray, advancing from one triangle to a neighboring one until the polygon boundary is reached. The key result of the paper is a Steiner triangulation of a simple polygon with the property that a ray can intersect at most O(log n) triangles before reaching the polygon boundary. We are able to compute such a triangulation in linear sequential time, or in O(log n) parallel time using O(n/log n) processors. This gives a simple, yet optimal, ray-shooting algorithm for a simple polygon. Using a well-known technique, we can extend our triangulation procedure to a multiconnected polygon with k components and n vertices, so that a ray intersects at most O(√k log n) triangles.     

Efficiently updating constrained Delaunay triangulations

TheConstrained Delaunay Triangulation of a set of obstacle line segments in the plane is the Delaunay triangulation of the endpoint set of these obstacles with the restriction that the edge set of the triangulation contains all these obstacles. In this paper we present an optimal (logn +k) algorithm for inserting an obstacle line segment or deleting an obstacle edge in the constrained Delaunay triangulation of a set ofn obstacle line segments in the plane. Herek is the number of Delaunay edges deleted and added in the triangulation during the updates.This work is supported by NSERC grant OPG0041629.     

The product of the idempotents and an $\mathcal{H}$-class of the finite full transformation semigroup

We investigate the set products S=EH, where E is the set of idempotents of a finite full transformation semigroup T _X and H is an arbitrary H\mathcal{H}-class of T _X . We show that S is a semigroup and is a union of H\mathcal{H}-classes of T _X . We determine the nature of this union through use of Hall’s Marriage Lemma. We describe Green’s relations and thereby show that S has regular elements of all possible ranks and that \operatornameReg(S)\operatorname{Reg}(S) forms a right ideal of S.     

Some inequalities involving quadratic forms of operator means

Let T and S be two self-adjoint positive invertible operators of a complex Hilbert space H. In this paper, we investigate some inequalities involving the quadratic forms of the weighted arithmetic and harmonic means of T and S. Application for operator entropies is also discussed.     

An Upper and a Lower Bound Theorem for Combinatorial 4-Manifolds

In this paper we prove two inequalities. The first one gives a lower bound for the Euler characteristic of a tight combinatorial 4-manifold M under the additional assumptions that |M| is 1-connected, that M is a subcomplex of H (M) , and that H (M) is a centrally symmetric and simplicial d -polytope. The second inequality relates the Euler characteristic with the number of vertices of a combinatorial 4-manifold admitting a fixed-point free involution. Furthermore, we construct a new and highly symmetric 12-vertex triangulation of S ² x S ² realizing equality in each of these inequalities. Received January 23, 1996, and in revised form September 13, 1996.     

Full Lutz twist along the binding of an open book

Let T denote a binding component of an open book (S, f){(\Sigma, \phi)} compatible with a closed contact 3-manifold (M, ξ). We describe an explicit open book (S￠, f￠){(\Sigma', \phi')} compatible with (M, ζ), where ζ is the contact structure obtained from ξ by performing a full Lutz twist along T. Here, (S￠, f￠){(\Sigma', \phi')} is obtained from (S, f){(\Sigma, \phi)} by a local modification near the binding.     

On SQ-Supplemented Subgroups of Finite Groups

Let G be a finite group and H ≤ G. The subgroup H is called: S-permutable in G if HP = PH for all Sylow subgroups P of G; S-permutably embedded in G if each Sylow subgroup of H is also a Sylow subgroup of some S-permutable subgroup of G.

Let H be a subgroup of a group G. Then we say that H is SQ-supplemented in G if G has a subgroup T and an S-permutably embedded subgroup C ≤ H such that HT = G and T ∩ H ≤ C.

We study the structure of G under the assumption that some subgroups of G are SQ-supplemented in G. Some known results are generalized.     

Compact operators on a Banach space into the space of almost periodic functions

LetS be a topological semigroup andAP(S) the space of continous complex almost periodic functions onS. We obtain characterizations of compact and weakly compact operators from a Banach spaceX into AP(S). For this we use the almost periodic compactification ofS obtained through uniform spaces. For a bounded linear operatorT fromX into AP(S), letT ₅, be the translate ofT bys inS defined byT ₅(x)=(Tx) ₅ . We define topologies on the space of bounded linear operators fromX into AP(S) and obtain the necessary and sufficient conditions for an operatorT to be compact or weakly compact in terms of the uniform continuity of the maps→T ₅. IfS is a Hausdorff topological semigroup, we also obtain characterizations of compact and weakly compact multipliers on AP(S) in terms of the uniform continuity of the map S→μ_s, where μ_s denotes the unique vector measure corresponding to the operatorT ₅.     

Existence and uniqueness of complete constant mean curvature surfaces at infinity ofH 3

A set of conditions are given, each equivalent to the constancy of mean curvature of a surface in H ³.It is shown that analogs of these equivalences exist for surfaces in S _∞ ² ,the bounding ideal sphere of H ³,leading to a notion of constant mean curvature at infinity of H ³.A parametrization of all complete constant mean curvature surfaces at infinity of H ³ is given by holomorphic quadratic differentials on Ĉ,C, and D.     

Finite Groups with Some Subgroups of Prime Power Order S-Quasinormally Embedded

Abstract

A subgroup of a group G is said to be S-quasinormal in G if it permutes with every Sylow subgroup of G. A subgroup H of a group G is said to be S-quasinormally embedded in G if every Sylow subgroup of H is a Sylow subgroup of some S-quasinormal subgroup of G. In this paper we examine the structure of a finite group G under the assumption that certain abelian subgroups of prime power order are S-quasinormally embedded in G. Our results improve and extend recent results of Ramadan [Ramadan, M. (2001). The influence of S-quasinormality of some subgroups of prime power order on the structure of finite groups. Arch. Math. 77:143–148].     

Torsion in the full orbifold <Emphasis Type="Italic">K</Emphasis>-theory of abelian symplectic quotients

Let (M, ω, Φ) be a Hamiltonian T-space and let H í T{H\subseteq T} be a closed Lie subtorus. Under some technical hypotheses on the moment map Φ, we prove that there is no additive torsion in the integral full orbifold K-theory of the orbifold symplectic quotient [M//H]. Our main technical tool is an extension to the case of moment map level sets the well-known result that components of the moment map of a Hamiltonian T-space M are Morse-Bott functions on M. As first applications, we conclude that a large class of symplectic toric orbifolds, as well as certain S ¹-quotients of GKM spaces, have integral full orbifold K-theory that is free of additive torsion. Finally, we introduce the notion of semilocally Delzant which allows us to formulate sufficient conditions under which the hypotheses of the main theorem hold. We illustrate our results using low-rank coadjoint orbits of type A and B.     

The geodetic number of the lexicographic product of graphs

A set S of vertices of a graph G is a geodetic set if every vertex of G lies in an interval between two vertices from S. The size of a minimum geodetic set in G is the geodetic number g(G) of G. We find that the geodetic number of the lexicographic product G°H for a non-complete graph H lies between 2 and 3g(G). We characterize the graphs G and H for which g(G°H)=2, as well as the lexicographic products T°H that enjoy g(T°H)=3g(G), when T is isomorphic to a tree. Using a new concept of the so-called geodominating triple of a graph G, a formula that expresses the exact geodetic number of G°H is established, where G is an arbitrary graph and H a non-complete graph.     

A Generalized Drinfeld Quantum Double Construction Based on Weak Hopf Algebras

Let B and H be weak Hopf algebras with bijective antipodes S _B and S _H , respectively. Based on a compatible weak Hopf dual pairing (B, H, σ), we construct a generalized Drinfeld quantum double 𝔻(B, H) which is a weak T-coalgebra over a twisted semi-direct square of groups. In particular, when B and H are finite dimensional and the above pairing map σ is nondegenerate, 𝔻(B, H) admits a nontrivial quasitriangular structure. Some explicit examples are given as an application of our theory.     

On the chromatic spectrum of acyclic decompositions of graphs

If G is any graph, a G‐decomposition of a host graph H = (V, E) is a partition of the edge set of H into subgraphs of H which are isomorphic to G. The chromatic index of a G‐decomposition is the minimum number of colors required to color the parts of the decomposition so that two parts which share a node get different colors. The G‐spectrum of H is the set of all chromatic indices taken on by G‐decompositions of H. If both S and T are trees, then the S‐spectrum of T consists of a single value which can be computed in polynomial time. On the other hand, for any fixed tree S, not a single edge, there is a unicyclic host whose S‐spectrum has two values, and if the host is allowed to be arbitrary, the S‐spectrum can take on arbitrarily many values. Moreover, deciding if an integer k is in the S‐spectrum of a general bipartite graph is NP‐hard. We show that if G has c > 1 components, then there is a host H whose G‐spectrum contains both 3 and 2c + 1. If G is a forest, then there is a tree T whose G‐spectrum contains both 2 and 2c. Furthermore, we determine the complete spectra of both paths and cycles with respect to matchings. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 83–104, 2007     

On the Connection Between the Projection and the Extension of a Parallelotope

This paper presents a result concerning the connection between the parallel projection P _v,H of a parallelotope P along the direction v (into a transversal hyperplane H) and the extension P + S(v), meaning the Minkowski sum of P and the segment S(v) = {λv | −1 ≤ λ ≤ 1}. A sublattice L _v of the lattice of translations of P associated to the direction v is defined. It is proved that the extension P + S(v) is a parallelotope if and only if the parallel projection P _v,H is a parallelotope with respect to the lattice of translations L _v,H , which is the projection of the lattice L _v along the direction v into the hyperplane H.     

A new simplicial variable dimension algorithm to find equilibria on the product space of unit simplices

A new simplicial variable dimension restart algorithm is introduced to solve the nonlinear complementarity problem on the product spaceS of unit simplices. The triangulation which underlies the algorithm differs from the triangulations ofS used thus far. Moreover, the number of rays along which the algorithm can leave the arbitrarily chosen starting point is much larger. More precisely, there is a ray leading from the starting point to each vertex ofS. In caseS is the product ofn one-dimensional unit simplices the alogrithm is similar to the octahedral algorithm onR ⁿ having 2 ⁿ rays. Also, the accuracy of an approximate solution in the terminal simplex of the algorithm is in general better than for the other algorithms onS. Computational results will show that the number of iterations for the new algorithm is much less. The examples concern the computation of equilibria in noncooperative games, exchange economies and trade models. This author is financially supported by the Netherlands Organisation for the Advancement of Pure Research (ZWO), Grant 46-98. This research is part of the VF-program “Equilibrium and Disequilibrium in Demand and Supply” which has been approved by the Netherlands ministry of education and sciences.     

On solubility and supersolubility of some classes of finite groups

Let G be a finite group and H a subgroup of G. Then H is said to be S-permutable in G if HP = PH for all Sylow subgroups P of G. Let HsG be the subgroup of H generated by all those subgroups of H which are S-permutable in G. Then we say that H is S-embedded in G if G has a normal subgroup T and an S-permutable subgroup C such that T ∩ H HsG and HT = C. Our main result is the following Theorem A. A group G is supersoluble if and only if for every non-cyclic Sylow subgroup P of the generalized Fitting subgrou...     

Multiplicative Lie Isomorphisms Between Prime Rings

Let ? be a prime ring with 1 containing a nontrivial idempotent E, and let ?′ be another prime ring. If Φ:? → ?′ is a multiplicative Lie isomorphism, then Φ(T + S) = Φ(T) + Φ(S) + Z′ _T,S for all T, S ∈ ?, where Z′ _T,S is an element in the center 𝒵′ of ?′ depending on T and S.     

Unitary dilations and theC* algebra0 2

LetH be an infinite-dimensional separable Hilbert space, and letS=(S _ij)∈teB(H)⊗M ₂ be a unitary 2 × 2 matrix with operator entries. We study theC*-algebra generated by the operatorsS _ij, and show that the study of unitary dilations of isometriesT inH reduces to the special case whereS ₁₁ =T, andS ₂₁ = 0. We useC*-algebraic techniques to obtain detailed results about the set of all unitary dilations ofT. Work supported in part by NSF.