Geometry of continued fractions associated with Frobenius numbers

The article describes the interrelations between the minimal integer number N(a,b,c) which belongs to the additive semigroup of integers generated by a, b, c together with all greater integers, on the one hand, and the geometrical theory of continued fractions describing the convex hulls of sets of integer points in simplicial cones, on the other hand. It also provides some hints on the extension of N to non-integral arguments.     

Choice,hull, continuity and fidelity

Continuity and fidelity (i.e., ‘path-independence’) conditions are studied for choices (picking subsets), hulls (picking supersets) and compositions of these. Examples of hulls are topological closure and convex hull, both of which are faithful. Using a continuity theorem of Sertel, a sufficient condition is given for closed convex hull, d, to be both continuous and faithful on the space of compact subsets of a locally convex topological vector space. A sufficient condition is also given for the joint continuity and fidelity of the composition, sd, of a choice, s, and d. In contrast with the Kalai and Megiddo theorem that singleton-valued maps of this form cannot be faithful and at the same time continuous on the space of finite subsets of Eⁿ, the conjunction of (upper semi-)continuity and fidelity is shown to be commonplace for choices or maps of the above form (not constrained to be singleton-valued).     

The traveling salesman problem with few inner points

We propose two algorithms for the planar Euclidean traveling salesman problem. The first runs in O(k!kn) time and O(k) space, and the second runs in O(2^kk²n) time and O(2^kkn) space, where n denotes the number of input points and k denotes the number of points interior to the convex hull.     

Noncanonical number systems in the integers

The well-known binary and decimal representations of the integers, and other similar number systems, admit many generalisations. Here, we investigate whether still every integer could have a finite expansion on a given integer base b, when we choose a digit set that does not contain 0. We prove that such digit sets exist and we provide infinitely many examples for every base b with |b|?4, and for b=−2. For the special case b=−2, we give a full characterisation of all valid digit sets.     

Primal Dividing and Dual Pruning: Output-Sensitive Construction of Four-Dimensional Polytopes and Three-Dimensional Voronoi Diagrams

In this paper, we give an algorithm for output-sensitive construction of an f-face convex hull of a set of n points in general position in E ⁴ . Our algorithm runs in time and uses O(n+f) space. This is the first algorithm within a polylogarithmic factor of optimal time over the whole range of f. By a standard lifting map, we obtain output-sensitive algorithms for the Voronoi diagram or Delaunay triangulation in E ³ and for the portion of a Voronoi diagram that is clipped to a convex polytope. Our approach simplifies the ``ultimate convex hull algorithm' of Kirkpatrick and Seidel in E ² and also leads to improved output-sensitive results on constructing convex hulls in E ^d for any even constant d > 4. Received August 3, 1995, and in revised form September 19, 1996.     

On the computation of the hull number of a graph

Let G be a graph. If u,v∈V(G), a u-vshortest path of G is a path linking u and v with minimum number of edges. The closed interval I[u,v] consists of all vertices lying in some u-v shortest path of G. For S⊆V(G), the set I[S] is the union of all sets I[u,v] for u,v∈S. We say that S is a convex set if I[S]=S. The convex hull of S, denoted I_h[S], is the smallest convex set containing S. A set S is a hull set of G if I_h[S]=V(G). The cardinality of a minimum hull set of G is the hull number of G, denoted by hn(G). In this work we prove that deciding whether hn(G)≤k is NP-complete.We also present polynomial-time algorithms for computing hn(G) when G is a unit interval graph, a cograph or a split graph.     

2-Selmer groups and the Birch-Swinnerton-Dyer Conjecture for the congruent number curves

We take an approach toward counting the number of integers n for which the curve En: y²=x³−n²x has 2-Selmer groups of a given size. This question was also discussed in a pair of papers by Roger Heath-Brown. In contrast to earlier work, our analysis focuses on restricting the number of prime factors of n. Additionally, we discuss the connection between computing the size of these Selmer groups and verifying cases of the Birch and Swinnerton-Dyer Conjecture. The key ingredient for the asymptotic formulae is the “independence” of the Legendre symbol evaluated at the prime divisors of an integer with exactly k prime factors.     

An algorithm for the separation of two-row cuts

We consider the question of finding deep cuts from a model with two rows of the type $P_I=\{(x,s)\in \mathbb{Z }^2\times \mathbb{R }^n_+ : x=f+Rs\}$ . To do that, we show how to reduce the complexity of setting up the polar of $\mathop {\mathrm{conv}}(P_I)$ from a quadratic number of integer hull computations to a linear number of integer hull computations. Furthermore, we present an algorithm that avoids computing all integer hulls. A polynomial running time is not guaranteed but computational results show that the algorithm runs quickly in practice.     

Computing the number of ways of representing primes by a norm form

Formulae for the number of different integral solutions ofa ²+b²+c²+d²+ac+bd=p are given wherep is a prime and the solution satisfies certain natural congruence conditions. Similar formulae are given for the case of the quadratic forma ²+b²+2c²+2d²+ac+bd.     

On a combinatorial method for counting smooth numbers in sets of integers

In this paper we develop a method for determining the number of integers without large prime factors lying in a given set S. We will apply it to give an easy proof that certain sufficiently dense sets A and B always produce the expected number of “smooth” sums a+b, a∈A, b∈B. The proof of this result is completely combinatorial and elementary.     

Canonical models for a class of polynomially convex hulls

We use holomorphic motions and Beltrami equation to study a class of polynomially convex hulls in ℂ ² with Jordan fibers over the disc D. It is shown that every such hull is biholomorphically equivalent to a unique (up to suitable normalisation) canonical model. These models are the hulls whose complements in D×ℂmacr; are biholomorphic to a bidisc and are further characterized in terms of capacity of the fibers, Green’s function, pseudoconcavity and approximability by (very) special analytic polyhedra. Received: 11 September 1995 / Revised version: 11 March 1996     

On the X-Y convex hull of a set of X-Y polygons

We study the class of rectilinear polygons, calledX – Y polygons, with horizontal and vertical edges, which are frequently used as building blocks for very large-scale integrated (VLSI) circuit layout and wiring. In the paper we introduce the notion of convexity within the class ofX – Y polygons and present efficient algorithms for computing theX – Y convex hulls of anX – Y polygon and of a set ofX – Y polygons under various conditions. Unlike convex hulls in the Euclidean plane, theX – Y convex hull of a set ofX – Y polygons may not exist. The condition under which theX – Y convex hull exists is given and an algorithm for testing if the given set ofX – Y polygons satisfies the condition is also presented.     

On the number of divisors of x2 + x + A

Let A be a positive or negative rational integer such that integers in the field of √1 ? 4A have unique prime factorization. An elementary criterion will be obtained for x² + x + A to be a prime number, where x is a positive integer. The criterion implies that for positive A the polynomial x² + x + A is prime for x = 0, 1,…, A ? 2.     

Computing Hereditary Convex Structures

Color red and blue the n vertices of a convex polytope \(\mathcal{P}\) in ?³. Can we compute the convex hull of each color class in o(nlog?n) time? What if we have more than two colors? What if the colors are random? Consider an arbitrary query halfspace and call the vertices of \(\mathcal{P}\) inside it blue: can the convex hull of the blue points be computed in time linear in their number? More generally, can we quickly compute the blue hull without looking at the whole polytope? This paper considers several instances of hereditary computation and provides new results for them. In particular, we resolve an eight-year old open problem by showing how to split a convex polytope in linear expected time.     

More on planar point subsets with a specified number of interior points

An interior point of a finite planar point set is a point of the set that is not on the boundary of the convex hull of the set. For any integer k ≥ 1, let g(k) be the smallest integer such that every set P of points in the plane with no three collinear points and with at least g(k) interior points has a subset containing precisely k interior point of P. We prove that g(k) ≥ 3k for k ≥ 3, which improves the known result that g(k) ≥ 3k ? 1 for k ≥ 3.     

Reducibility number

Let P be a poset in a class of posets P. A smallest positive integer r is called reducibility number of P with respect to P if there exists a non-empty subset S of P with |S|=r and P-S∈P. The reducibility numbers for the power set 2ⁿ of an n-set (n?2) with respect to the classes of distributive lattices, modular lattices and Boolean lattices are calculated. Also, it is shown that the reducibility number r of the lattice of all subgroups of a finite group G with respect to the class of all distributive lattices is 1 if and only if the order of G has at most two distinct prime divisors; further if r is a prime number then order of G is divisible by exactly three distinct primes. The class of pseudo-complemented u-posets is shown to be reducible. Deletable elements in semidistributive posets are characterized.     

The Randomized Integer Convex Hull

Let K R^d be a sufficiently round convex body (the ratio of the circumscribed ball to the inscribed ball is bounded by a constant) of a sufficiently large volume. We investigate the randomized integer convex hull I_L(K) = conv (K L), where L is a randomly translated and rotated copy of the integer lattice Z^d. We estimate the expected number of vertices of I_L(K), whose behaviour is similar to the expected number of vertices of the convex hull of Vol K random points in K. In the planar case we also describe the expectation of the missed area Vol (K \ I_L(K)). Surprisingly, for K a polygon, the behaviour in this case is different from the convex hull of random points.     

Topological convexities, selections and fixed points

A convexity on a set X is a family of subsets of X which contains the whole space and the empty set as well as the singletons and which is closed under arbitrary intersections and updirected unions. A uniform convex space is a uniform topological space endowed with a convexity for which the convex hull operator is uniformly continuous. Uniform convex spaces with homotopically trivial polytopes (convex hulls of finite sets) are absolute extensors for the class of metric spaces; if they are completely metrizable then a continuous selection theorem à la Michael holds. Upper semicontinuous maps have approximate selections and fixed points, under the usual assumptions.     

Cyclic permutations and nearly symmetric integer vectors

Given an integer vector x^T=(x₁,…,x_n) with the property x₁>x₂>? >x_n>0, it is shown that the convex hull of the n cyclic permutations of x contains all the nearly symmetric integer vectors majorized by x. A generalization to noninteger vectors and an application to a class of integer symmetric optimization problems are also given.