Fitting a Set of Points by a Circle

Given a set of points S={p ₁ ,. . ., p _n } in Euclidean d -dimensional space, we address the problem of computing the d -dimensional annulus of smallest width containing the set. We give a complete characterization of the centers of annuli which are locally minimal in arbitrary dimension and we show that, for d=2 , a locally minimal annulus has two points on the inner circle and two points on the outer circle that interlace anglewise as seen from the center of the annulus. Using this characterization, we show that, given a circular order of the points, there is at most one locally minimal annulus consistent with that order and it can be computed in time O(n log n) using a simple algorithm. Furthermore, when points are in convex position, the problem can be solved in optimal Θ(n) time. Received June 25, 1997, and in revised form March 5, 1998.     

Applications of a semi-dynamic convex hull algorithm

We obtain new results for manipulating and searching semi-dynamic planar convex hulls (subject to deletions only), and apply them to derive improved bounds for two problems in geometry and scheduling. The new convex hull results are logarithmic time bounds for set splitting and for finding a tangent when the two convex hulls are not linearly separated. Using these results, we solve the following two problems optimally inO(n logn) time: (1) [matching] givenn red points andn blue points in the plane, find a matching of red and blue points (by line segments) in which no two edges cross, and (2) [scheduling] givenn jobs with due dates, linear penalties for late completion, and a single machine on which to process them, find a schedule of jobs that minimizes the maximum penalty.     

Complementing a finite subgroup of a hyperbolic group by a free factor

We give necessary and sufficient conditions for a finite subgroup H of a hyperbolic group G to contain a free subgroup F of rank two in G such that F and H generate a free product F ∗ H. A verification algorithm for these conditions is pointed out.     

On induced subgraphs of a block

If G is a block, then a vertex u of G is called critical if G - u is not a block. In this article, relationships between the localization of critical vertices and the localization of vertices of relatively small degrees (especially, of degree two) are studied. A block is called semicritical if a) each edge is incident with at least one critical vertex and b) each vertex of degree two is critical. Let G be a semicritical block with at least six vertices. It is proved that A) there exist distinct vertices u₂, v₁, u₂, and v₂ of degree two in G such that u₁v₁ and u₂v₂ are edges of G, and u₁v₂, and u₂v₂ are edges of the complement of G, and B) the complement of G is a block with no critical vertex of degree two.     

Homogenization of a fully coupled thermoelasticity problem for a highly heterogeneous medium with a priori known phase transformations

We investigate a linear, fully coupled thermoelasticity problem for a highly heterogeneous, two‐phase medium. The medium in question consists of a connected matrix with disconnected, initially periodically distributed inclusions separated by a sharp interface undergoing an a priori known interface movement because of phase transformations. After transforming the moving geometry to an ? ‐periodic, fixed reference domain, we establish the well‐posedness of the model and derive a number of ? ‐independent a priori estimates. Via a two‐scale convergence argument, we then show that the ? ‐dependent solutions converge to solutions of a corresponding upscaled model with distributed time‐dependent microstructures. Copyright © 2017 John Wiley & Sons, Ltd.     

Some extensions of a hypergraph

It is shown how to construct a vertex-transitive hypergraphX ^* from a suitable collection of isomorphic copies of a given hypergraphX by identifying one or none of the vertices of every two copies in the collection. MoreoverX ^* andX have the same strong chromatic number.If the hypergraphX is edge-coloured, thenX ^* can be so constructed that it is strongly vertex-colour-transitive. This paper also considers the case where a section hypergraph or none of the vertices of every two isomorphic copies is identified in the construction ofX ^*.     

Embedding a Pair of Graphs in a Surface, and the Width of 4-dimensional Prismatoids

A prismatoid is a polytope with all its vertices contained in two parallel facets, called its bases. Its width is the number of steps needed to go from one base to the other in the dual graph. The first author recently showed that the existence of counter-examples to the Hirsch conjecture is equivalent to that of d-prismatoids of width larger than d, and constructed such prismatoids in dimension five. Here we show that the same is impossible in dimension four. This is proved by looking at the pair of graph embeddings on a 2-sphere that arise from the normal fans of the two bases of Q.     

Covering a set with homothets of a convex body

We consider two problems mentioned in the book “Research Problems in Discrete Geometry” (Brass et al. in research problems in discrete geometry, vol xii+499. Springer, New York, pp ISBN: 978-0387-23815-8; 0-387-23815-8, 2005). First, let K and L be given convex bodies in \mathbbR^d{\mathbb{R}^{d}} . We prove that if the total volume of a family of positive homothets of K is sufficiently large then they permit a translative covering of L. This problem, in the case when K = L and the dimension is two, was originally posed by L. Fejes Tóth. The previously known bound (Januszewski in proc. of the International scientific conference on mathematics, pp 29–34. Žilina, 1998) on the total volume (in the case when K = L) was of order d ^d vol(K), we prove a bound that is exponential in the dimension. The second problem is the following: Find a condition, in terms of the coefficients of homothety, that is necessary for a family of positive homothets of K to cover K. The problem was phrased by V. Soltan, who conjectured that the sum of the coefficients is at least d. We confirm an asymptotic version of this conjecture.     

Diameter of a direct power of a finite group

We present two conjectures concerning the diameter of a direct power of a finite group. The first conjecture states that the diameter of Gⁿ with respect to each generating set is at most n(|G|?rank(G)); and the second one states that there exists a generating set 𝒜, of minimum size, for Gⁿ such that the diameter of Gⁿ with respect to 𝒜 is at most n(|G|?rank(G)). We will establish evidence for each of the above mentioned conjectures.     

A note on a Brill-Noether locus over a non-hyperelliptic curve of genus 4

We prove that a certain Brill-Noether locus over a non-hyperelliptic curve C of genus 4, is isomorphic to the Donagi-Izadi cubic threefold in the case when the pencils of the two trigonal line bundles of C coincide.     

Packing two copies of a sparse graph into a graph with restrained maximum degree

We show that if a tree T is not a star, then there is an embedding σ of T in the complement of T such that the maximum degree of T∪σ(T) is at most Δ(T)+2. We also show that if G is a graph of order n with n?1 edges, then with several exceptions, there exists an embedding σ of G in the complement of G such that the maximum degree of G∪σ(G) is at most Δ(G)+3. Both results are sharp in the sense that neither of Δ(T)+2 and Δ(G)+3 can be reduced. From these two results, we deduce two corollaries on packings of three graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 178–187, 2009     

Optimal threshold policies in a workload model with a variable number of service phases per job

We consider an M|E _N |1 queue in which there are two essential on-line decisions that have to be taken. The first one is the decision to either accept or reject new jobs. The second one is the decision to either continue or abort the service of a job. We show that under certain regularity conditions, there exist optimal threshold policies for these two types of decisions.     

Some results on the genus of a group

This Note announces two results on the genus of a group. First, there is exactly one group of genus two, thus answering a question of V. K. Proulx. Second, the genus of the full symmetric group of degree n is n!/168 + 1, for all n > 167.     

Calculating a function of a matrix with a real spectrum

Let T be a square matrix with a real spectrum, and let f be an analytic function. The problem of the approximate calculation of f(T) is discussed. Applying the Schur triangular decomposition and the reordering, one can assume that T is triangular and its diagonal entries t_ii are arranged in increasing order. To avoid calculations using the differences t_ii ? t_jj with close (including equal) t_ii and t_jj, it is proposed to represent T in a block form and calculate the two main block diagonals using interpolating polynomials. The rest of the f(T) entries can be calculated using the Parlett recurrence algorithm. It is also proposed to perform some scalar operations (such as the building of interpolating polynomials) with an enlarged number of significant decimal digits.

     

On a characteristic property of minimal-ruled surfaces

LetS be a surface of classC ⁴ in 3-dimensional Euclidean space. In this paper it is shown that any two of the following three conditions imply the third one: (a)S is a minimal surface, (b) Two families of Laguerre lines ofS form a conjugate net, (c)S is a non-developable ruled surface. Furthermore, it is proved that any surface (other than a sphere, a cylinder of revolution and a plane) of constant mean curvature on which the two families of Laguerre lines form a conjugate net is a minimal-helicoid.     

Equipartition of a continuous mass distribution

Here are three samples of results. (1) Let m be a finite (absolutely) continuous mass distribution in ℝ², and let ℓ = {ℓ₁, ..., ℓ₅ ⊂ ℝ²} be a quintuple of rays with common origin such that any two adjacent angles between them make a sum of at most π. Then an affine image of ℓ subdivides m into five parts with any prescribed ratios. (2) For each finite continuous mass distribution m in ℝⁿ, there exist n mutually orthogonal hyperplanes any two of which quarter m. (3) Let m and m′ be two finite continuous mass distributions in ℝRⁿ with common center of symmetry O. Then there exist n hyperplanes through O any two of which quarter both m and m′. Bibliography: 9 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 329, 2005, pp. 92–106.     

Estimating a general function of a quadratic function

Let be an observation from a spherically symmetric distribution with unknown location parameter . For a general non-negative function c, we consider the problem of estimating c(||x − θ||²) under the usual quadratic loss. For p ≥ 5, we give sufficient conditions for improving on the unbiased estimator γ₀ of c(||x − θ||²) by competing estimators γ _s = γ₀ + s correcting γ₀ with a suitable function s. The main condition relies on a partial differential inequality of the form k Δs + s ² ≤ 0 for a certain constant k ≠ 0. Our approach unifies, in particular, the two problems of quadratic loss estimation and confidence statement estimation and allows to derive new results for these two specific cases. Note that we formally establish our domination results (that is, with no recourse to simulation).      

Vector Lattices on a Set of Two Generators

It is proved that the center of an automorphism group Aut(FVL2) of a free vector lattice FVL2 on a set of two free generators is isomorphic to a multiplicative group of positive reals. It is shown that the free vector lattice FVL2 has an isomorphic representation by continuous piecewise linear functions of the real line; as a consequence, the ideal lattice and the root system for rectifying ideals in FVL2 are amply described. Similar results are obtained for a free vector lattice FVL2 _Q 2 generated by two elements over a field of rational numbers.     

Partitioning the Vertices of a Graph into Two Total Dominating Sets

A total dominating set in a graph G is a set S of vertices of G such that every vertex in G is adjacent to a vertex of S. We study graphs whose vertex set can be partitioned into two total dominating sets. In particular, we develop several sufficient conditions for a graph to have a vertex partition into two total dominating sets. We also show that with the exception of the cycle on five vertices, every selfcomplementary graph with minimum degree at least two has such a partition.     

Packing two forests into a bipartite graph

For two integers a and b, we say that a bipartite graph G admits an (a, b)-bipartition if G has a bipartition (X, Y) such that |X| = a and |Y| = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this note, we prove that any two compatible trees of order n can be packed into a complete bipartite graph of order at most n + 1. We also provide a family of infinitely many pairs of compatible trees which cannot be packed into a complete bipartite graph of the same order. A theorem about packing two forests into a complete bipartite graph is derived from this result. © 1996 John Wiley & Sons, Inc.