240 results on '"Swanepoel, Konrad"'
Search Results
2. The number of small-degree vertices in matchstick graphs
- Author
-
Lavollée, Jérémy and Swanepoel, Konrad J.
- Subjects
Mathematics - Combinatorics ,Computer Science - Computational Geometry ,52C10 (Primary) 05C10 (Secondary) - Abstract
A matchstick graph is a crossing-free unit-distance graph in the plane. Harborth (1981) proposed the problem of determining whether there exists a matchstick graph in which every vertex has degree exactly $5$. In 1982, Blokhuis gave a proof of non-existence. A shorter proof was found by Kurz and Pinchasi (2011) using a charging method. We combine their method with the isoperimetric inequality to show that there are $\Omega(\sqrt{n})$ vertices in a matchstick graph on $n$ vertices that are of degree at most $4$, which is asymptotically tight.
- Published
- 2022
3. Contacts in totally separable packings in the plane and in high dimensions
- Author
-
Naszódi, Márton and Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics - Abstract
We study the contact structure of totally separable} packings of translates of a convex body $K$ in $\mathbb{R}^d$, that is, packings where any two touching bodies have a separating hyperplane that does not intersect the interior of any translate in the packing. The separable Hadwiger number $H_{\text{sep}}(K)$ of $K$ is defined to be the maximum number of translates touched by a single translate, with the maximum taken over all totally separable packings of translates of $K$. We show that for each $d\geq 8$, there exists a smooth and strictly convex $K$ in $\mathbb{R}^d$ with $H_{\text{sep}}(K)>2d$, and asymptotically, $H_{\text{sep}}(K)=\Omega\bigl((3/\sqrt{8})^d\bigr)$. We show that Alon's packing of Euclidean unit balls such that each translate touches at least $2^{\sqrt{d}}$ others whenever $d$ is a power of $4$, can be adapted to give a totally separable packing of translates of the $\ell_1$-unit ball with the same touching property. We also consider the maximum number of touching pairs in a totally separable packing of $n$ translates of any planar convex body $K$. We prove that the maximum equals $\lfloor 2n-2\sqrt{n}\rfloor$ if and only if $K$ is a quasi hexagon, thus completing the determination of this value for all planar convex bodies., Comment: 12 pages, 5 figures. Pdf generation issue fixed, no change to first version
- Published
- 2022
- Full Text
- View/download PDF
4. A Tight Bound for the Number of Edges of Matchstick Graphs
- Author
-
Lavollée, Jérémy and Swanepoel, Konrad
- Published
- 2023
- Full Text
- View/download PDF
5. Bounding the number of edges of matchstick graphs
- Author
-
Lavollée, Jérémy and Swanepoel, Konrad J.
- Subjects
Mathematics - Combinatorics ,Computer Science - Computational Geometry ,52C10 (Primary), 05C10 (Secondary) - Abstract
We show that a matchstick graph with $n$ vertices has no more than $3n-c\sqrt{n-1/4}$ edges, where $c=\frac12(\sqrt{12} + \sqrt{2\pi\sqrt{3}})$. The main tools in the proof are the Euler formula, the isoperimetric inequality, and an upper bound for the number of edges in terms of $n$ and the number of non-triangular faces. We also find a sharp upper bound for the number of triangular faces in a matchstick graph., Comment: 9 pages, 3 figures
- Published
- 2021
6. Angular measures and Birkhoff orthogonality in Minkowski planes
- Author
-
Naszódi, Márton, Prokaj, Vilmos, and Swanepoel, Konrad
- Subjects
Mathematics - Metric Geometry ,Mathematics - Functional Analysis ,Primary 52A21, Secondary 28A75, 46B20 - Abstract
Let $x$ and $y$ be two unit vectors in a normed plane $\mathbb{R}^2$. We say that $x$ is Birkhoff orthogonal to $y$ if the line through $x$ in the direction $y$ supports the unit disc. A B-measure (Fankh\"anel 2011) is an angular measure $\mu$ on the unit circle for which $\mu(C)=\pi/2$ whenever $C$ is a shorter arc of the unit circle connecting two Birkhoff orthogonal points. We present a characterization of the normed planes that admit a B-measure.
- Published
- 2019
7. Outer linear measure of connected sets via Steiner trees
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Mathematics - History and Overview ,28A75 - Abstract
We resurrect an old definition of the linear measure of a metric continuum in terms of Steiner trees, independently due to Menger (1930) and Choquet (1938). We generalise it to any metric space and provide a proof of a little-known theorem of Choquet that it coincides with the outer linear measure for any connected metric space. As corollaries we obtain simple proofs of Go{\l}\k{a}b's theorem (1928) on the lower semicontinuity of linear measure of continua and a theorem of Bogn\'ar (1989) on the linear measure of the closure of a set. We do not use any measure theory apart from the definition of outer linear measure., Comment: 21 pages, 7 figures
- Published
- 2019
8. Favourite distances in 3-space
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Combinatorics ,Computer Science - Computational Geometry ,Mathematics - Metric Geometry ,52C10 - Abstract
Let $S$ be a set of $n$ points in Euclidean $3$-space. Assign to each $x\in S$ a distance $r(x)>0$, and let $e_r(x,S)$ denote the number of points in $S$ at distance $r(x)$ from $x$. Avis, Erd\H{o}s and Pach (1988) introduced the extremal quantity $f_3(n)=\max\sum_{x\in S}e_r(x,S)$, where the maximum is taken over all $n$-point subsets $S$ of 3-space and all assignments $r\colon S\to(0,\infty)$ of distances. We show that if the pair $(S,r)$ maximises $f_3(n)$ and $n$ is sufficiently large, then, except for at most $2$ points, $S$ is contained in a circle $\mathcal{C}$ and the axis of symmetry $\mathcal{L}$ of $\mathcal{C}$, and $r(x)$ equals the distance from $x$ to $C$ for each $x\in S\cap\mathcal{L}$. This, together with a new construction, implies that $f_3(n)=n^2/4 + 5n/2 + O(1)$., Comment: 10 pages, 4 figures
- Published
- 2019
9. Ordinary hyperspheres and spherical curves
- Author
-
Lin, Aaron and Swanepoel, Konrad
- Subjects
Mathematics - Combinatorics ,52C10 - Abstract
An ordinary hypersphere of a set of points in real $d$-space, where no $d+1$ points lie on a $(d-2)$-sphere or a $(d-2)$-flat, is a hypersphere (including the degenerate case of a hyperplane) that contains exactly $d+1$ points of the set. Similarly, a $(d+2)$-point hypersphere of such a set is one that contains exactly $d+2$ points of the set. We find the minimum number of ordinary hyperspheres, solving the $d$-dimensional spherical analogue of the Dirac--Motzkin conjecture for $d \geqslant 3$. We also find the maximum number of $(d+2)$-point hyperspheres in even dimensions, solving the $d$-dimensional spherical analogue of the orchard problem for even $d \geqslant 4$., Comment: 10 pages. Final version
- Published
- 2019
- Full Text
- View/download PDF
10. Shortest directed networks in the plane
- Author
-
Maxwell, Alastair and Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Computer Science - Computational Geometry ,Mathematics - Combinatorics ,Mathematics - Optimization and Control ,05C20, 49Q10, 52A40, 90B10 - Abstract
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., Comment: 21 pages, 14 figures. To appear in Graphs and Combinatorics
- Published
- 2019
11. On sets defining few ordinary hyperplanes
- Author
-
Lin, Aaron and Swanepoel, Konrad
- Subjects
Mathematics - Combinatorics ,Mathematics - Algebraic Geometry ,52C10, 52C35 - Abstract
Let $P$ be a set of $n$ points in real projective $d$-space, not all contained in a hyperplane, such that any $d$ points span a hyperplane. An ordinary hyperplane of $P$ is a hyperplane containing exactly $d$ points of $P$. We show that if $d\ge 4$, the number of ordinary hyperplanes of $P$ is at least $\binom{n-1}{d-1} - O_d(n^{\lfloor(d-1)/2\rfloor})$ if $n$ is sufficiently large depending on $d$. This bound is tight, and given $d$, we can calculate the exact minimum number for sufficiently large $n$. This is a consequence of a structure theorem for sets with few ordinary hyperplanes: For any $d \ge 4$ and $K > 0$, if $n \ge C_d K^8$ for some constant $C_d > 0$ depending on $d$ and $P$ spans at most $K\binom{n-1}{d-1}$ ordinary hyperplanes, then all but at most $O_d(K)$ points of $P$ lie on a hyperplane, an elliptic normal curve, or a rational acnodal curve. We also find the maximum number of $(d+1)$-point hyperplanes, solving a $d$-dimensional analogue of the orchard problem. Our proofs rely on Green and Tao's results on ordinary lines, our earlier work on the $3$-dimensional case, as well as results from classical algebraic geometry., Comment: 34 pages
- Published
- 2018
- Full Text
- View/download PDF
12. Ordinary planes, coplanar quadruples, and space quartics
- Author
-
Lin, Aaron and Swanepoel, Konrad
- Subjects
Mathematics - Combinatorics ,Mathematics - Algebraic Geometry ,52C10, 52C35, 14H50 - Abstract
An ordinary plane of a finite set of points in real 3-space with no three collinear is a plane intersecting the set in exactly three points. We prove a structure theorem for sets of points spanning few ordinary planes. Our proof relies on Green and Tao's work on ordinary lines in the plane, combined with classical results on space quartic curves and non-generic projections of curves. This gives an alternative approach to Ball's recent results on ordinary planes, as well as extending them. We also give bounds on the number of coplanar quadruples determined by a finite set of points on a rational space quartic curve in complex 3-space, answering a question of Raz, Sharir and De Zeeuw [Israel J. Math. 227 (2018)].
- Published
- 2018
- Full Text
- View/download PDF
13. Embedding graphs in Euclidean space
- Author
-
Frankl, Nóra, Kupavskii, Andrey, and Swanepoel, Konrad J.
- Subjects
Mathematics - Combinatorics ,Mathematics - Metric Geometry ,52C10 - Abstract
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\H{o}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}$., Comment: 11 pages
- Published
- 2018
- Full Text
- View/download PDF
14. Bounding the size of an almost-equidistant set in Euclidean space
- Author
-
Kupavskii, Andrey, Mustafa, Nabil H., and Swanepoel, Konrad J.
- Subjects
Mathematics - Combinatorics ,Computer Science - Discrete Mathematics ,Mathematics - Metric Geometry ,52C10 - Abstract
A set of points in d-dimensional Euclidean space is almost equidistant if among any three points of the set, some two are at distance 1. We show that an almost-equidistant set in $\mathbb{R}^d$ has cardinality $O(d^{4/3})$., Comment: 6 pages
- Published
- 2017
- Full Text
- View/download PDF
15. Almost-equidistant sets
- Author
-
Balko, Martin, Pór, Attila, Scheucher, Manfred, Swanepoel, Konrad, and Valtr, Pavel
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,Primary 52C10, Secondary 05C30, 05C55, 05C85 - Abstract
For a positive integer $d$, a set of points in $d$-dimensional Euclidean space is called almost-equidistant if for any three points from the set, some two are at unit distance. Let $f(d)$ denote the largest size of an almost-equidistant set in $d$-space. It is known that $f(2)=7$, $f(3)=10$, and that the extremal almost-equidistant sets are unique. We give independent, computer-assisted proofs of these statements. It is also known that $f(5) \ge 16$. We further show that $12\leq f(4)\leq 13$, $f(5)\leq 20$, $18\leq f(6)\leq 26$, $20\leq f(7)\leq 34$, and $f(9)\geq f(8)\geq 24$. Up to dimension $7$, our work is based on various computer searches, and in dimensions $6$ to $9$, we give constructions based on the known construction for $d=5$. For every dimension $d \ge 3$, we give an example of an almost-equidistant set of $2d+4$ points in the $d$-space and we prove the asymptotic upper bound $f(d) \le O(d^{3/2})$., Comment: 24 pages, 9 figures. Accepted by Graphs and Combinatorics
- Published
- 2017
16. Arrangements of homothets of a convex body II
- Author
-
Naszódi, Márton and Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,52A37 - Abstract
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
- Published
- 2017
- Full Text
- View/download PDF
17. Combinatorial distance geometry in normed spaces
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,52C10 (primary), 46B20, 52A20, 52A21 (secondary) - Abstract
We survey problems and results from combinatorial geometry in normed spaces, concentrating on problems that involve distances. These include various properties of unit-distance graphs, minimum-distance graphs, diameter graphs, as well as minimum spanning trees and Steiner minimum trees. In particular, we discuss translative kissing (or Hadwiger) numbers, equilateral sets, and the Borsuk problem in normed spaces. We show how to use the angular measure of Peter Brass to prove various statements about Hadwiger and blocking numbers of convex bodies in the plane, including some new results. We also include some new results on thin cones and their application to distinct distances and other combinatorial problems for normed spaces., Comment: 43 pages, 4 figures, New Trends in Intuitive Geometry, Springer, to appear
- Published
- 2017
- Full Text
- View/download PDF
18. Arrangements of homothets of a convex body
- Author
-
Naszódi, Márton, Pach, János, and Swanepoel, Konrad
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,Mathematics - Functional Analysis ,52A20 (Primary), 46B20, 52A21, 52C17 (Secondary) - Abstract
Answering a question of F\"uredi and Loeb (1994), we show that the maximum number of pairwise intersecting homothets of a $d$-dimensional centrally symmetric convex body $K$, none of which contains the center of another in its interior, is at most $O(3^d d\log d)$. If $K$ is not necessarily centrally symmetric and the role of its center is played by its centroid, then the above bound can be replaced by $O(3^d\binom{2d}{d}d\log d)$. We establish analogous results for the case where the center is defined as an arbitrary point in the interior of $K$. We also show that in the latter case, one can always find families of at least $\Omega((2/\sqrt{3})^d)$ translates of $K$ with the above property., Comment: 13 pages, 2 figures. Accepted by Mathematika
- Published
- 2016
- Full Text
- View/download PDF
19. On sets defining few ordinary circles
- Author
-
Lin, Aaron, Makhul, Mehdi, Mojarrad, Hossein Nassajian, Schicho, Josef, Swanepoel, Konrad, and de Zeeuw, Frank
- Subjects
Mathematics - Combinatorics ,Mathematics - Algebraic Geometry ,52C10 - Abstract
An ordinary circle of a set $P$ of $n$ points in the plane is defined as a circle that contains exactly three points of $P$. We show that if $P$ is not contained in a line or a circle, then $P$ spans at least $\frac{1}{4}n^2 - O(n)$ ordinary circles. Moreover, we determine the exact minimum number of ordinary circles for all sufficiently large $n$ and describe all point sets that come close to this minimum. We also consider the circle variant of the orchard problem. We prove that $P$ spans at most $\frac{1}{24}n^3 - O(n^2)$ circles passing through exactly four points of $P$. Here we determine the exact maximum and the extremal configurations for all sufficiently large $n$. These results are based on the following structure theorem. If $n$ is sufficiently large depending on $K$, and $P$ is a set of $n$ points spanning at most $Kn^2$ ordinary circles, then all but $O(K)$ points of $P$ lie on an algebraic curve of degree at most four. Our proofs rely on a recent result of Green and Tao on ordinary lines, combined with circular inversion and some classical results regarding algebraic curves., Comment: 28 pages, 6 figures. Post-publication corrections to Theorems 1.3 and 1.5 with corresponding updates to Sections 4.1 and 4.2. The earlier preprint arXiv:1412.8314 is subsumed by this paper and will not be published independently
- Published
- 2016
- Full Text
- View/download PDF
20. Sphere-of-influence graphs in normed spaces
- Author
-
Naszódi, Márton, Pach, János, and Swanepoel, Konrad
- Subjects
Mathematics - Metric Geometry ,46B20 - Abstract
We show that any $k$-th closed sphere-of-influence graph in a $d$-dimensional normed space has a vertex of degree less than~$5^d k$, thus obtaining a common generalization of results of F\"uredi and Loeb (1994) and Guibas, Pach and Sharir (1994)., Comment: 3 pages
- Published
- 2016
- Full Text
- View/download PDF
21. Approximate Euclidean Steiner Trees
- Author
-
Ras, Charl, Swanepoel, Konrad J., and Thomas, Doreen
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,Mathematics - Optimization and Control ,90C35 (Primary), 05C05, 90B10 (Secondary) - Abstract
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., Comment: 24 pages, 9 figures
- Published
- 2016
- Full Text
- View/download PDF
22. Triangles of nearly equal area
- Author
-
Swanepoel, Konrad J.
- Published
- 2021
- Full Text
- View/download PDF
23. Embedding graphs in Euclidean space
- Author
-
Frankl, Nóra, Kupavskii, Andrey, and Swanepoel, Konrad J.
- Published
- 2020
- Full Text
- View/download PDF
24. Double-normal pairs in the plane and on the sphere
- Author
-
Pach, János and Swanepoel, Konrad J.
- Subjects
Mathematics - Combinatorics ,Mathematics - Metric Geometry ,52C10 - Abstract
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., Comment: 19 pages, 10 figures
- Published
- 2014
- Full Text
- View/download PDF
25. Double-normal pairs in space
- Author
-
Pach, János and Swanepoel, Konrad
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,52C10 - Abstract
A double-normal pair of a finite set $S$ of points from $R^d$ 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$ perpendicular to $pq$. A double-normal pair $pq$ is strict if $S\setminus\{p,q\}$ lies in the open strip. The problem of estimating the maximum number $N_d(n)$ of double-normal pairs in a set of $n$ points in $R^d$, was initiated by Martini and Soltan (2006). It was shown in a companion paper that in the plane, this maximum is $3\lfloor n/2\rfloor$, for every $n>2$. For $d\geq 3$, it follows from the Erd\H{o}s-Stone theorem in extremal graph theory that $N_d(n)=\frac12(1-1/k)n^2 + o(n^2)$ for a suitable positive integer $k=k(d)$. Here we prove that $k(3)=2$ and, in general, $\lceil d/2\rceil \leq k(d)\leq d-1$. Moreover, asymptotically we have $\lim_{n\rightarrow\infty}k(d)/d=1$. The same bounds hold for the maximum number of strict double-normal pairs., Comment: 15 pages, 1 figure
- Published
- 2014
- Full Text
- View/download PDF
26. Angular measures and Birkhoff orthogonality in Minkowski planes
- Author
-
Naszódi, Márton, Prokaj, Vilmos, and Swanepoel, Konrad
- Published
- 2020
- Full Text
- View/download PDF
27. Shortest Directed Networks in the Plane
- Author
-
Maxwell, Alastair and Swanepoel, Konrad J.
- Published
- 2020
- Full Text
- View/download PDF
28. Almost-Equidistant Sets
- Author
-
Balko, Martin, Pór, Attila, Scheucher, Manfred, Swanepoel, Konrad, and Valtr, Pavel
- Published
- 2020
- Full Text
- View/download PDF
29. Equilateral sets and a Sch\'utte Theorem for the 4-norm
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Mathematics - Functional Analysis ,Primary 46B20, Secondary 52A21, 52C17 - Abstract
A well-known theorem of Sch\"utte (1963) gives a sharp lower bound for the ratio between the maximum distance and minimum distance between n+2 points in n-dimensional Euclidean space. In this brief note we adapt B\'ar\'any's elegant proof of this theorem to the space $\ell_4^n$. This gives a new proof that the largest cardinality of an equilateral set in $\ell_4^n$ is n+1, and gives a constructive bound for an interval $(4-\epsilon_n,4+\epsilon_n)$ of values of p close to 4 for which it is guaranteed that the largest cardinality of an equilateral set in $\ell_p^n$ is n+1., Comment: 7 pages. Some technical details added
- Published
- 2013
- Full Text
- View/download PDF
30. Combinatorial Distance Geometry in Normed Spaces
- Author
-
Swanepoel, Konrad J., Fejes Tóth, Gabor, Editor-in-Chief, Ambrus, Gergely, Series Editor, Katona, Gyula, Editorial Board Member, Lovász, László, Editorial Board Member, Miklós, Dezső, Editorial Board Member, Pálfy, Péter Pal, Editorial Board Member, Recski, Andras, Editorial Board Member, Stipsicz, András, Editorial Board Member, Szász, Domokos, Editorial Board Member, Bárány, Imre, editor, Böröczky, Károly J., editor, Fejes Tóth, Gábor, editor, and Pach, János, editor
- Published
- 2018
- Full Text
- View/download PDF
31. Sphere-of-Influence Graphs in Normed Spaces
- Author
-
Naszódi, Márton, Pach, János, Swanepoel, Konrad, Conder, Marston D. E., editor, Deza, Antoine, editor, and Weiss, Asia Ivić, editor
- Published
- 2018
- Full Text
- View/download PDF
32. Sets of unit vectors with small subset sums
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,Mathematics - Functional Analysis ,52A37 (Primary) 05C15, 15A03, 15A45, 46B20, 49Q10, 52A21, 52A40, 52A41 (Secondary) - Abstract
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\"uredi, 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\'edi Theorem, the Brunn-Minkowski inequality, and lower bounds for the rank of a perturbation of the identity matrix., Comment: 41 pages
- Published
- 2012
- Full Text
- View/download PDF
33. Generalised k-Steiner Tree Problems in Normed Planes
- Author
-
Brazil, Marcus N., Ras, Charl J., Swanepoel, Konrad J., and Thomas, Doreen A.
- Subjects
Mathematics - Combinatorics ,Computer Science - Data Structures and Algorithms - Abstract
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.
- Published
- 2011
- Full Text
- View/download PDF
34. Maximal equilateral sets
- Author
-
Swanepoel, Konrad J. and Villa, Rafael
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,Mathematics - Functional Analysis ,46B20 (Primary) 46B85, 52A21, 52C17 (Secondary) - Abstract
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 $\Gamma$, $m(\ell_p(\Gamma))$ 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$., Comment: 15 pages. This version incorporates some suggestions from a referee obtained after galley proofs. Equations (18) and (23) are corrected
- Published
- 2011
- Full Text
- View/download PDF
35. Absorbing angles, Steiner minimal trees, and antipodality
- Author
-
Martini, Horst, Swanepoel, Konrad J., and de Wet, P. Oloff
- Subjects
Mathematics - Metric Geometry ,Mathematics - Functional Analysis ,46B20 (Primary). 05C05, 49Q10, 52A21 (Secondary) - Abstract
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$., Comment: 7 pages, 4 figures. An old paper already published in 2009. This is a preprint version
- Published
- 2011
- Full Text
- View/download PDF
36. Favourite distances in high dimensions
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Combinatorics ,Mathematics - Metric Geometry ,52C10 - Abstract
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\"os 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\"os and Pach (1988) and Erd\"os 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$., Comment: 17 pages
- Published
- 2011
- Full Text
- View/download PDF
37. Large convexly independent subsets of Minkowski sums
- Author
-
Swanepoel, Konrad J. and Valtr, Pavel
- Subjects
Mathematics - Combinatorics ,Mathematics - Metric Geometry ,Primary 52C10. Secondary 52A10 - Abstract
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 \Omega(n\sqrt{\log n})$, which answers a question of Eisenbrand, Pach, Rothvo\ss, 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)=\Theta(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., Comment: 7 pages
- Published
- 2010
38. Midpoint sets contained in the unit sphere of a normed space
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Primary 52A15, Secondary 52A20 - Abstract
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., Comment: 11 pages, 5 figures
- Published
- 2010
- Full Text
- View/download PDF
39. Sets of unit vectors with small pairwise sums
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Mathematics - Functional Analysis ,Primary 46B20. Secondary 52A21, 52B10 - Abstract
We study the sizes of delta-additive sets of unit vectors in a d-dimensional normed space: the sum of any two vectors has norm at most delta. One-additive sets originate in finding upper bounds of vertex degrees of Steiner Minimum Trees in finite dimensional smooth normed spaces (Z. F\"uredi, J. C. Lagarias, F. Morgan, 1991). We show that the maximum size of a delta-additive set over all normed spaces of dimension d grows exponentially in d for fixed delta>2/3, stays bounded for delta<2/3, and grows linearly at the threshold delta=2/3. Furthermore, the maximum size of a 2/3-additive set in d-dimensional normed space has the sharp upper bound of d, with the single exception of spaces isometric to three-dimensional l^1 space, where there exists a 2/3-additive set of four unit vectors., Comment: 6 pages. Old paper of 10 years ago
- Published
- 2010
- Full Text
- View/download PDF
40. Embedding a Latin square with transversal into a projective space
- Author
-
Pretorius, Lou M. and Swanepoel, Konrad J.
- Subjects
Mathematics - Combinatorics ,05B15 (Primary), 51A45 (Secondary) - Abstract
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., Comment: 11 pages. This is the revised final preprint version. Added journal reference and doi
- Published
- 2010
- Full Text
- View/download PDF
41. Helly-type Theorems for Hollow Axis-aligned Boxes
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Combinatorics ,52A35 - Abstract
A hollow axis-aligned box is the boundary of the cartesian product of $d$ compact intervals in R^d. We show that for d\geq 3, if any 2^d of a collection of hollow axis-aligned boxes have non-empty intersection, then the whole collection has non-empty intersection; and if any 5 of a collection of hollow axis-aligned rectangles in R^2 have non-empty intersection, then the whole collection has non-empty intersection. The values 2^d for d\geq 3 and 5 for d=2 are the best possible in general. We also characterize the collections of hollow boxes which would be counterexamples if 2^d were lowered to 2^d-1, and 5 to 4, respectively., Comment: 7 pages. Old paper from 1999
- Published
- 2009
- Full Text
- View/download PDF
42. On the existence of shortest directed networks
- Author
-
Swanepoel, Konrad J
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,05C20 ,49Q10 - Abstract
A directed network connecting a set A to a set B is a digraph containing an a-b path for each a in A and b in B. Vertices in the directed network not in A or B are called Steiner points. We show that in a finitely compact metric space in which geodesics exist, any two finite sets A and B are connected by a shortest directed network. We also bound the number of Steiner points by a function of the sizes of A and B. Previously, such an existence result was known only for the Euclidean plane [M. Alfaro, Pacific J. Math. 167 (1995) 201-214]. The main difficulty is that, unlike the undirected case (Steiner minimal trees), the underlying graphs need not be acyclic. Existence in the undirected case was first shown by E. J. Cockayne [Canad. Math. Bull. 10 (1967) 431-450]., Comment: 6 pages. An old paper from 2000
- Published
- 2008
43. Simultaneous packing and covering in sequence spaces
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Mathematics - Functional Analysis ,46B20 (primary), 52C17 (secondary) - Abstract
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., Comment: 5 pages
- Published
- 2008
- Full Text
- View/download PDF
44. Balancing unit vectors
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,52A40 - Abstract
Theorem A. Let $x_1,...,x_{2k+1}$ be unit vectors in a normed plane. Then there exist signs $\epsi_1,...,\epsi_{2k+1}\in\{\pm 1\}$ such that $\norm{\sum_{i=1}^{2k+1}\epsi_i x_i}\leq 1$. We use the method of proof of the above theorem to show the following point facility location result, generalizing Proposition 6.4 of Y. S. Kupitz and H. Martini (1997). Theorem B. Let $p_0,p_1,...,p_n$ be distinct points in a normed plane such that for any $1\leq i
- Published
- 2008
- Full Text
- View/download PDF
45. Cardinalities of k-distance sets in Minkowski spaces
- Author
-
Swanepoel, Konrad J.
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,52C10 - Abstract
A subset of a metric space is a k-distance set if there are exactly k non-zero distances occuring between points. We conjecture that a k-distance set in a d-dimensional Banach space (or Minkowski space), contains at most (k+1)^d points, with equality iff the unit ball is a parallelotope. We solve this conjecture in the affirmative for all 2-dimensional spaces and for spaces where the unit ball is a parallelotope. For general spaces we find various weaker upper bounds for k-distance sets., Comment: 7 pages, 2 figures
- Published
- 2007
- Full Text
- View/download PDF
46. The geometry of Minkowski spaces -- a survey. Part I
- Author
-
Martini, Horst, Swanepoel, Konrad J, and Weiss, Gunter
- Subjects
Mathematics - Metric Geometry ,Mathematics - Functional Analysis ,52A21 (Primary), 46B07, 46B20 (Secondary) - Abstract
We survey elementary results in Minkowski spaces (i.e. finite dimensional Banach spaces) that deserve to be collected together, and give simple proofs for some of them. We place special emphasis on planar results. Many of these results have often been rediscovered as lemmas to other results. In Part I we cover the following topics: The triangle inequality and consequences such as the monotonicity lemma, geometric characterizations of strict convexity, normality (Birkhoff orthogonality), conjugate diameters and Radon curves, equilateral triangles and the affine regular hexagon construction, equilateral sets, circles: intersection, circumscribed, characterizations, circumference and area, inscribed equilateral polygons., Comment: 56 pages, 28 figures
- Published
- 2007
- Full Text
- View/download PDF
47. Extremal Problems in Minkowski Space related to Minimal Networks
- Author
-
Swanepoel, Konrad J
- Subjects
Mathematics - Metric Geometry ,Mathematics - Functional Analysis ,52A40 (Primary) 52A21, 49Q10 (Secondary) - Abstract
We solve the following problem of Z. F\"uredi, J. C. Lagarias and F. Morgan [FLM]: Is there an upper bound polynomial in $n$ for the largest cardinality of a set S of unit vectors in an n-dimensional Minkowski space (or Banach space) such that the sum of any subset has norm less than 1? We prove that |S|\leq 2n and that equality holds iff the space is linearly isometric to \ell^n_\infty, the space with an n-cube as unit ball. We also remark on similar questions raised in [FLM] that arose out of the study of singularities in length-minimizing networks in Minkowski spaces., Comment: 6 pages. 11-year old paper. Implicit question in the last sentence has been answered in Discrete & Computational Geometry 21 (1999) 437-447
- Published
- 2007
- Full Text
- View/download PDF
48. The Fermat-Torricelli problem in normed planes and spaces
- Author
-
Martini, Horst, Swanepoel, Konrad J, and Weiss, Gunter
- Subjects
Mathematics - Optimization and Control ,Mathematics - Metric Geometry ,90B85 (Primary) 46B20, 52A01, 52A21 (Secondary) - Abstract
We investigate the Fermat-Torricelli problem in d-dimensional real normed spaces or Minkowski spaces, mainly for d=2. Our approach is to study the Fermat-Torricelli locus in a geometric way. We present many new results, as well as give an exposition of known results that are scattered in various sources, with proofs for some of them. Together, these results can be considered to be a minitheory of the Fermat-Torricelli problem in Minkowski spaces and especially in Minkowski planes. This demonstrates that substantial results about locational problems valid for all norms can be found using a geometric approach.
- Published
- 2007
- Full Text
- View/download PDF
49. Unit distances and diameters in Euclidean spaces
- Author
-
Swanepoel, Konrad J
- Subjects
Mathematics - Metric Geometry ,Mathematics - Combinatorics ,52C10 - Abstract
We show that the maximum number of unit distances or of diameters in a set of n points in d-dimensional Euclidean space is attained only by specific types of Lenz constructions, for all d >= 4 and n sufficiently large, depending on d. As a corollary we determine the exact maximum number of unit distances for all even d >= 6, and the exact maximum number of diameters for all d >= 4, for all $n$ sufficiently large, depending on d.
- Published
- 2007
- Full Text
- View/download PDF
50. A new proof of Vazsonyi's conjecture
- Author
-
Swanepoel, Konrad J
- Subjects
Mathematics - Combinatorics ,Mathematics - Metric Geometry ,52C10 (Primary). 05C10 (Secondary) - Abstract
We present a self-contained proof that the number of diameter pairs among n points in Euclidean 3-space is at most 2n-2. The proof avoids the ball polytopes used in the original proofs by Grunbaum, Heppes and Straszewicz. As a corollary we obtain that any three-dimensional diameter graph can be embedded in the projective plane., Comment: 4 pages
- Published
- 2007
- Full Text
- View/download PDF
Catalog
Discovery Service for Jio Institute Digital Library
For full access to our library's resources, please sign in.