Source author record

Konrad J. Swanepoel

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.MG math.CO math.FA math.OC Computational Geometry Data Structures and Algorithms

Catalog footprint

Research overview

15works

6topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Penny graphs in the hyperbolic plane

We consider the problem of finding the maximum number $e_d(n)$ of pairs of touching circles in a packing of $n$ congruent circles of diameter $d$ in the hyperbolic plane of curvature $-1$ . In the Euclidean plane, the maximum comes from a spiral construction of the tiling of the plane with equilateral triangles (Harborth 1974), with a similar result in the hyperbolic plane for the values of $d$ corresponding to the order- $k$ triangular tilings (Bowen 2000). We present various upper and lower bounds for $e_d(n)$ for all values of $d > 0$ . In particular, we prove that if $d > 0.66114\dots$ except for $d=0.76217\dots$ , then the number of touching pairs is less than the one coming from a spiral construction in the order- $7$ triangular tiling, which we conjecture to be extremal. We also give a lower bound $e_d(n) > (2+\varepsilon_d)n$ where $\varepsilon_d > 1$ for all $d > 0$ .

preprint2020arXiv

Shortest directed networks in the plane

Given a set of sources and a set of sinks as points in the Euclidean plane, a directed network is a directed graph drawn in the plane with a directed path from each source to each sink. Such a network may contain nodes other than the given sources and sinks, called Steiner points. We characterize the local structure of the Steiner points in all shortest-length directed networks in the Euclidean plane. This characterization implies that these networks are constructible by straightedge and compass. Our results build on unpublished work of Alfaro, Campbell, Sher, and Soto from 1989 and 1990. Part of the proof is based on a new method that uses other norms in the plane. This approach gives more conceptual proofs of some of their results, and as a consequence, we also obtain results on shortest directed networks for these norms.

preprint2018arXiv

Embedding graphs in Euclidean space

The dimension of a graph $G$ is the smallest $d$ for which its vertices can be embedded in $d$ -dimensional Euclidean space in the sense that the distances between endpoints of edges equal $1$ (but there may be other unit distances). Answering a question of Erdős and Simonovits [Ars Combin. 9 (1980) 229--246], we show that any graph with less than $\binom{d+2}{2}$ edges has dimension at most $d$ . Improving their result, we prove that that the dimension of a graph with maximum degree $d$ is at most $d$ . We show the following Ramsey result: if each edge of the complete graph on $2d$ vertices is coloured red or blue, then either the red graph or the blue graph can be embedded in Euclidean $d$ -space. We also derive analogous results for embeddings of graphs into the $(d-1)$ -dimensional sphere of radius $1/\sqrt{2}$ .

preprint2017arXiv

Arrangements of homothets of a convex body II

A family of homothets of an o-symmetric convex body K in d-dimensional Euclidean space is called a Minkowski arrangement if no homothet contains the center of any other homothet in its interior. We show that any pairwise intersecting Minkowski arrangement of a d-dimensional convex body has at most $2\cdot 3^d$ members. This improves a result of Polyanskii (arXiv:1610.04400). Using similar ideas, we also give a proof the following result of Polyanskii: Let $K_1,\dots,K_n$ be a sequence of homothets of the o-symmetric convex body $K$ , such that for any $i<j$ , the center of $K_j$ lies on the boundary of $K_i$ . Then $n\leq O(3^d d)$ .

preprint2016arXiv

Approximate Euclidean Steiner Trees

An approximate Steiner tree is a Steiner tree on a given set of terminals in Euclidean space such that the angles at the Steiner points are within a specified error e from 120 degrees.This notion arises in numerical approximations of minimum Steiner trees (W. D. Smith, Algorithmica, 7 (1992), 137--177). We investigate the worst-case relative error of the length of an approximate Steiner tree compared to the shortest tree with the same topology.Rubinstein, Weng and Wormald (J. Global Optim. 35 (2006), 573--592) conjectured that this relative error is at most linear in $e$ , independent of the number of terminals. We verify their conjecture for the two-dimensional case as long as the error $e$ is sufficiently small in terms of the number of terminals. We derive a lower bound linear in $e$ for the relative error in the two-dimensional case when $e$ is sufficiently small in terms of the number of terminals. We find improved estimates of the relative error for larger values of $e$ , and calculate exact values in the plane for three and four terminals.

preprint2014arXiv

Double-normal pairs in the plane and on the sphere

A double-normal pair of a finite set $S$ of points from Euclidean space is a pair of points $\{p,q\}$ from $S$ such that $S$ lies in the closed strip bounded by the hyperplanes through $p$ and $q$ that are perpendicular to $pq$ . A double-normal pair $pq$ is strict if $S\setminus\{p,q\}$ lies in the open strip. We answer a question of Martini and Soltan (2006) by showing that a set of $n\geq 3$ points in the plane has at most $3\lfloor n/2\rfloor$ double-normal pairs. This bound is sharp for each $n\geq 3$ . In a companion paper, we have asymptotically determined this maximum for points in $R^3$ . Here we show that if the set lies on some 2-sphere, it has at most $17n/4 - 6$ double-normal pairs. This bound is attained for infinitely many values of $n$ . We also establish tight bounds for the maximum number of strict double-normal pairs in a set of $n$ points in the plane and on the sphere.

preprint2014arXiv

Sets of unit vectors with small subset sums

We say that a family ${x_i|i\in[m]}$ of vectors in a Banach space $X$ satisfies the $k$ -collapsing condition if $|\sum_{i\in I}x_i|\leq 1$ for all $k$ -element subsets $I\subseteq{1,2,...,m}$ . Let $C(k,d)$ denote the maximum cardinality of a $k$ -collapsing family of unit vectors in a $d$ \dimensional Banach space, where the maximum is taken over all spaces of dimension $d$ . Similarly, let $CB(k,d)$ denote the maximum cardinality if we require in addition that $\sum_{i=1}^m x_i=o$ . The case $k=2$ was considered by Füredi, Lagarias and Morgan (1991). These conditions originate in a theorem of Lawlor and Morgan (1994) on geometric shortest networks in smooth finite-dimensional Banach spaces. We show that $CB(k,d)=\max{k+1,2d}$ for all $k,d\geq 2$ . The behaviour of $C(k,d)$ is not as simple, and we derive various upper and lower bounds for various ranges of $k$ and $d$ . These include the exact values $C(k,d)=\max{k+1,2d}$ in certain cases. We use a variety of tools from graph theory, convexity and linear algebra in the proofs: in particular the Hajnal-Szemerédi Theorem, the Brunn-Minkowski inequality, and lower bounds for the rank of a perturbation of the identity matrix.

preprint2013arXiv

Generalised k-Steiner Tree Problems in Normed Planes

The 1-Steiner tree problem, the problem of constructing a Steiner minimum tree containing at most one Steiner point, has been solved in the Euclidean plane by Georgakopoulos and Papadimitriou using plane subdivisions called oriented Dirichlet cell partitions. Their algorithm produces an optimal solution within $O(n^2)$ time. In this paper we generalise their approach in order to solve the $k$ -Steiner tree problem, in which the Steiner minimum tree may contain up to $k$ Steiner points for a given constant $k$ . We also extend their approach further to encompass other normed planes, and to solve a much wider class of problems, including the $k$ -bottleneck Steiner tree problem and other generalised $k$ -Steiner tree problems. We show that, for any fixed $k$ , such problems can be solved in $O(n^{2k})$ time.

preprint2013arXiv

Maximal equilateral sets

A subset of a normed space $X$ is called equilateral if the distance between any two points is the same. Let $m(X)$ be the smallest possible size of an equilateral subset of $X$ maximal with respect to inclusion. We first observe that Petty's construction of a $d$ -dimensional $X$ of any finite dimension $d\geq 4$ with $m(X)=4$ can be generalised to give $m(X\oplus_1\mathbb{R})=4$ for any $X$ of dimension at least 2 which has a smooth point on its unit sphere. By a construction involving Hadamard matrices we then show that for any set $Γ$ , $m(\ell_p(Γ))$ is finite and bounded above by a function of $p$ , for all $1\leq p<2$ . Also, for all $p\in[1,\infty)$ and $d\in\mathbb{N}$ there exists $c=c(p,d)>1$ such that $m(X)\leq d+1$ for all $d$ -dimensional $X$ with Banach-Mazur distance less than $c$ from $\ell_p^d$ . Using Brouwer's fixed-point theorem we show that $m(X)\leq d+1$ for all $d$ -dimensional $X$ with Banach-Mazur distance less than 3/2 from $\ell_\infty^d$ . A graph-theoretical argument furthermore shows that $m(\ell_\infty^d)=d+1$ . The above results lead us to conjecture that $m(X)\leq 1+\dim X$ for all finite-dimensional normed spaces $X$ .

preprint2011arXiv

Absorbing angles, Steiner minimal trees, and antipodality

We give a new proof that a star $\{op_i:i=1,...,k\}$ in a normed plane is a Steiner minimal tree of its vertices $\{o,p_1,...,p_k\}$ if and only if all angles formed by the edges at o are absorbing [Swanepoel, Networks \textbf{36} (2000), 104--113]. The proof is more conceptual and simpler than the original one. We also find a new sufficient condition for higher-dimensional normed spaces to share this characterization. In particular, a star $\{op_i: i=1,...,k\}$ in any CL-space is a Steiner minimal tree of its vertices $\{o,p_1,...,p_k\}$ if and only if all angles are absorbing, which in turn holds if and only if all distances between the normalizations $\frac{1}{\|p_i\|}p_i$ equal 2. CL-spaces include the mixed $\ell_1$ and $\ell_\infty$ sum of finitely many copies of $R^1$ .

preprint2011arXiv

Embedding a Latin square with transversal into a projective space

A Latin square of side n defines in a natural way a finite geometry on 3n points, with three lines of size n and n^2 lines of size 3. A Latin square of side n with a transversal similarly defines a finite geometry on 3n+1 points, with three lines of size n, n^2-n lines of size 3, and n concurrent lines of size 4. A collection of k mutually orthogonal Latin squares defines a geometry on kn points, with k lines of size n and n^2 lines of size k. Extending work of Bruen and Colbourn (J. Combin. Th. Ser. A 92 (2000), 88-94), we characterise embeddings of these finite geometries into projective spaces over skew fields.

preprint2011arXiv

Favourite distances in high dimensions

Let $S$ be a set of $n$ points in $d$ -dimensional Euclidean space. Assign to each $x\in S$ an arbitrary distance $r(x)>0$ . Let $e_r(x,S)$ denote the number of points in $S$ at distance $r(x)$ from $x$ . Avis, Erdös and Pach (1988) introduced the extremal quantity $f_d(n)=\max\sum_{x\in S}e_r(x,S)$ , where the maximum is taken over all $n$ -point sets $S$ in $d$ -dimensional space and all assignments $r\colon S\to(0,\infty)$ of distances. We give a quick derivation of the asymptotics of the error term of $f_d(n)$ using only the analogous asymptotics of the maximum number of unit distance pairs in a set of $n$ points, which improves on previous results of Avis, Erdös and Pach (1988) and Erdös and Pach (1990). Then we prove a stability result for $d\geq 4$ , asserting that if $(S,r)$ with $|S|=n$ satisfies $e_r(S)=f_d(n)-o(n^2)$ , then, up to $o(n)$ points, $S$ is a Lenz construction with $r$ constant. Finally we use stability to show that for $n$ sufficiently large (depending on $d$ ) the pairs $(S,r)$ that attain $f_d(n)$ are up to scaling exactly the Lenz constructions that maximise the number of unit distance pairs with $r\equiv 1$ , with some exceptions in dimension 4. Analogous results hold for the furthest neighbour digraph, where $r$ is fixed to be $r(x)=\max_{y\in S} |xy|$ for $x\in S$ .

preprint2010arXiv

Large convexly independent subsets of Minkowski sums

Let $E_d(n)$ be the maximum number of pairs that can be selected from a set of $n$ points in $R^d$ such that the midpoints of these pairs are convexly independent. We show that $E_2(n)\geq Ω(n\sqrt{\log n})$ , which answers a question of Eisenbrand, Pach, Rothvoß, and Sopher (2008) on large convexly independent subsets in Minkowski sums of finite planar sets, as well as a question of Halman, Onn, and Rothblum (2007). We also show that $\lfloor\frac{1}{3}n^2\rfloor\leq E_3(n)\leq \frac{3}{8}n^2+O(n^{3/2})$ . Let $W_d(n)$ be the maximum number of pairwise nonparallel unit distance pairs in a set of $n$ points in some $d$ -dimensional strictly convex normed space. We show that $W_2(n)=Θ(E_2(n))$ and for $d\geq 3$ that $W_d(n)\sim\frac12\left(1-\frac{1}{a(d)}\right)n^2$ , where $a(d)\in N$ is related to strictly antipodal families. In fact we show that the same asymptotics hold without the requirement that the unit distance pairs form pairwise nonparallel segments, and also if diameter pairs are considered instead of unit distance pairs.

preprint2010arXiv

Midpoint sets contained in the unit sphere of a normed space

The midpoint set M(S) of a set S of points is the set of all midpoints of pairs of points in S. We study the largest cardinality of a midpoint set M(S) in a finite-dimensional normed space, such that M(S) is contained in the unit sphere, and S is outside the closed unit ball. We show in three dimensions that this maximum (if it exists) is determined by the facial structure of the unit ball. In higher dimensions no such relationship exists. We also determine the maximum for euclidean and sup norm spaces.

preprint2008arXiv

Simultaneous packing and covering in sequence spaces

We adapt a construction of Klee (1981) to find a packing of unit balls in $\ell_p$ ( $1\leq p<\infty$ ) which is efficient in the sense that enlarging the radius of each ball to any $R>2^{1-1/p}$ covers the whole space. We show that the value $2^{1-1/p}$ is optimal.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Konrad J. Swanepoel

Research overview

Is this your work?

15 publications

Penny graphs in the hyperbolic plane

Shortest directed networks in the plane

Embedding graphs in Euclidean space

Arrangements of homothets of a convex body II

Approximate Euclidean Steiner Trees

Double-normal pairs in the plane and on the sphere

Sets of unit vectors with small subset sums

Generalised k-Steiner Tree Problems in Normed Planes

Maximal equilateral sets

Absorbing angles, Steiner minimal trees, and antipodality

Embedding a Latin square with transversal into a projective space

Favourite distances in high dimensions

Large convexly independent subsets of Minkowski sums

Midpoint sets contained in the unit sphere of a normed space

Simultaneous packing and covering in sequence spaces

See the researcher in context

Building this map preview