Arrangements on Parametric Surfaces II: Concretizations and Applications

We describe the algorithms and implementation details involved in the concretizations of a generic framework that enables exact construction, maintenance, and manipulation of arrangements embedded on certain two-dimensional orientable parametric surfaces in three-dimensional space. The fundamentals of the framework are described in a companion paper. Our work covers arrangements embedded on elliptic quadrics and cyclides induced by intersections with other algebraic surfaces, and a specialized case of arrangements induced by arcs of great circles embedded on the sphere. We also demonstrate how such arrangements can be used to accomplish various geometric tasks efficiently, such as computing the Minkowski sums of polytopes, the envelope of surfaces, and Voronoi diagrams embedded on parametric surfaces. We do not assume general position. Namely, we handle degenerate input, and produce exact results in all cases. Our implementation is realized using Cgal and, in particular, the package that provides the underlying framework. We have conducted experiments on various data sets, and documented the practical efficiency of our approach.     

Spin order in paired quantum Hall states

We consider quantum Hall states at even-denominator filling fractions, especially nu=5/2, in the limit of small Zeeman energy. Assuming that a paired quantum Hall state forms, we study spin ordering and its interplay with pairing. We give numerical evidence that at nu=5/2 an incompressible ground state will exhibit spontaneous ferromagnetism. The Ginzburg-Landau (GL) theory for the spin degrees of freedom of paired Hall states is a perturbed CP2 model. We compute the coefficients in the GL theory by a BCS Stoner mean-field theory for coexisting order parameters, and show that even if repulsion is smaller than that required for a Stoner instability, ferromagnetic fluctuations can induce a partially or fully polarized superconducting state.     

Magnetic study of the UPt3 superconducting phases

In order to distinguish the UPt₃ superconducting (s.c.) phases we have studied their magnetic properties at low fields in a SQUID magnetometer and up to fields >H_c2(0) with a capacitive torque-meter. With the SQUID we measure the magnetic penetration depth and find the second s.c. transition at T_c⁻ when the field is applied along the c-axis, but not with . This result, combined with power-law behavior at low temperature T, is most consistent with the two-dimensional E_2u s.c. order parameter. Below 20 mK we find an additional diamagnetic signal that we ascribe to the normal state magnetism. In high fields our torque measurements show a kink of the perpendicular magnetization component at the B–C phase line, pointing to an enhanced Ginzburg–Landau parameter in the C phase.     

Signatures of a Concentration‐Dependent Flory χ Parameter: Swelling and Collapse of Coils and Brushes

The quality of solvents of polymers is often described in terms of the Flory χ parameter typically assumed to depend only on the temperature, T. In certain polymer‐solvent systems fitting the experimental data enforces the replacement of (χT) by a concentration‐dependent χ_eff. In turn, this modifies the swelling and collapse behavior. These effects are studied, in the framework of a mean‐field theory, for isolated coils and for planar brushes. The ϕ dependence of χ_eff gives rise to three main consequences: (i) shift in the cross‐over between Gaussian and self‐avoidance regimes; (ii) a possibility of first‐order collapse transition for isolated flexible coils; (iii) the possibility of a first‐order phase transition leading to a vertical phase separation within the brush. The discussion relates these effects directly to thermodynamic measurements and does not involve a specific microscopic model. The implementation for the case of poly(N‐isopropylamide) (PNIPAM) brushes is discussed.

ϕ vs. z plots, for brushes with N = 300, σ/a² = 18 (σ/R = 0.019) characterized by different χ_eff.     

On the Exact Maximum Complexity of Minkowski Sums of Polytopes

We present a tight bound on the exact maximum complexity of Minkowski sums of polytopes in ?³. In particular, we prove that the maximum number of facets of the Minkowski sum of k polytopes with m ₁,m ₂,…,m _k facets, respectively, is bounded from above by \(\sum_{1\leq i. Given k positive integers m ₁,m ₂,…,m _k , we describe how to construct k polytopes with corresponding number of facets, such that the number of facets of their Minkowski sum is exactly \(\sum_{1\leq i. When k=2, for example, the expression above reduces to 4m ₁ m ₂?9m ₁?9m ₂+26.     

Deconstructing Approximate Offsets

We consider the offset-deconstruction problem: Given a polygonal shape?Q with n vertices, can it be expressed, up to a tolerance??? in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution?P; then, P??s offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(nlogn)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. A variant of the algorithm, which we have implemented using the cgal library, is based on rational arithmetic and answers the same deconstruction problem up to an uncertainty parameter ??; its running time additionally depends on ??. If the input shape is found to be approximable, this algorithm also computes an approximate solution for the problem. It also allows us to solve parameter-optimization problems induced by the offset-deconstruction problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution?P with at most one more vertex than a vertex-minimal one.     

On large semi-linked graphs

Let H$H$ be a multigraph, possibly with loops, and consider a set S⊆V(H)$S\subseteq V\left(H\right)$. A (simple) graph G$G$ is (H,S)$(H,S)$-semi-linked   if, for every injective map f:S→V(G)$f:S\to V\left(G\right)$, there exists an injective map g:V(H)?S→V(G)?f(S)$g:V\left(H\right)?S\to V\left(G\right)?f\left(S\right)$ and a set of |E(H)|$\left|E\left(H\right)\right|$ internally disjoint paths in G$G$ connecting pairs of vertices of  f(S)∪g(V(H)?S)$f\left(S\right)\cup g(V\left(H\right)?S)$ for every edge between the corresponding vertices of H$H$. This new concept of (H,S)$(H,S)$-semi-linkedness is a generalization of H$H$-linkedness  . We establish a sharp minimum degree condition for a sufficiently large graph G$G$ to be (H,S)$(H,S)$-semi-linked.