TY - GEN
AB - The input to the token swapping problem is a graph with vertices v1, v2, . . . , vn, and n tokens with labels 1,2, . . . , n, one on each vertex. The goal is to get token i to vertex vi for all i= 1, . . . , n using a minimum number of swaps, where a swap exchanges the tokens on the endpoints of an edge.Token swapping on a tree, also known as “sorting with a transposition tree,” is not known to be in P nor NP-complete. We present some partial results:
1. An optimum swap sequence may need to perform a swap on a leaf vertex that has the correct token (a “happy leaf”), disproving a conjecture of Vaughan.
2. Any algorithm that fixes happy leaves—as all known approximation algorithms for the problem do—has approximation factor at least 4/3. Furthermore, the two best-known 2-approximation algorithms have approximation factor exactly 2.
3. A generalized problem—weighted coloured token swapping—is NP-complete on trees, but solvable in polynomial time on paths and stars. In this version, tokens and vertices have colours, and colours have weights. The goal is to get every token to a vertex of the same colour, and the cost of a swap is the sum of the weights of the two tokens involved.
AU - Biniaz, Ahmad
AU - Jain, Kshitij
AU - Lubiw, Anna
AU - Masárová, Zuzana
AU - Miltzow, Tillmann
AU - Mondal, Debajyoti
AU - Naredla, Anurag Murty
AU - Tkadlec, Josef
AU - Turcotte, Alexi
ID - 7950
T2 - arXiv:1903.06981
TI - Token swapping on trees
ER -
TY - JOUR
AB - The order-k Voronoi tessellation of a locally finite set 𝑋⊆ℝ𝑛 decomposes ℝ𝑛 into convex domains whose points have the same k nearest neighbors in X. Assuming X is a stationary Poisson point process, we give explicit formulas for the expected number and total area of faces of a given dimension per unit volume of space. We also develop a relaxed version of discrete Morse theory and generalize by counting only faces, for which the k nearest points in X are within a given distance threshold.
AU - Edelsbrunner, Herbert
AU - Nikitenko, Anton
ID - 5678
IS - 4
JF - Discrete and Computational Geometry
SN - 01795376
TI - Poisson–Delaunay Mosaics of Order k
VL - 62
ER -
TY - JOUR
AB - We answer a question of David Hilbert: given two circles it is not possible in general to construct their centers using only a straightedge. On the other hand, we give infinitely many families of pairs of circles for which such construction is possible.
AU - Akopyan, Arseniy
AU - Fedorov, Roman
ID - 6050
JF - Proceedings of the American Mathematical Society
TI - Two circles and only a straightedge
VL - 147
ER -
TY - JOUR
AB - We give non-degeneracy criteria for Riemannian simplices based on simplices in spaces of constant sectional curvature. It extends previous work on Riemannian simplices, where we developed Riemannian simplices with respect to Euclidean reference simplices. The criteria we give in this article are in terms of quality measures for spaces of constant curvature that we develop here. We see that simplices in spaces that have nearly constant curvature, are already non-degenerate under very weak quality demands. This is of importance because it allows for sampling of Riemannian manifolds based on anisotropy of the manifold and not (absolute) curvature.
AU - Dyer, Ramsay
AU - Vegter, Gert
AU - Wintraecken, Mathijs
ID - 6515
IS - 1
JF - Journal of Computational Geometry
SN - 1920-180X
TI - Simplices modelled on spaces of constant curvature
VL - 10
ER -
TY - JOUR
AB - We use the canonical bases produced by the tri-partition algorithm in (Edelsbrunner and Ölsböck, 2018) to open and close holes in a polyhedral complex, K. In a concrete application, we consider the Delaunay mosaic of a finite set, we let K be an Alpha complex, and we use the persistence diagram of the distance function to guide the hole opening and closing operations. The dependences between the holes define a partial order on the cells in K that characterizes what can and what cannot be constructed using the operations. The relations in this partial order reveal structural information about the underlying filtration of complexes beyond what is expressed by the persistence diagram.
AU - Edelsbrunner, Herbert
AU - Ölsböck, Katharina
ID - 6608
JF - Computer Aided Geometric Design
TI - Holes and dependences in an ordered complex
VL - 73
ER -
TY - CONF
AB - Fejes Tóth [5] and Schneider [9] studied approximations of smooth convex hypersurfaces in Euclidean space by piecewise flat triangular meshes with a given number of vertices on the hypersurface that are optimal with respect to Hausdorff distance. They proved that this Hausdorff distance decreases inversely proportional with m 2/(d−1), where m is the number of vertices and d is the dimension of Euclidean space. Moreover the pro-portionality constant can be expressed in terms of the Gaussian curvature, an intrinsic quantity. In this short note, we prove the extrinsic nature of this constant for manifolds of sufficiently high codimension. We do so by constructing an family of isometric embeddings of the flat torus in Euclidean space.
AU - Vegter, Gert
AU - Wintraecken, Mathijs
ID - 6628
T2 - The 31st Canadian Conference in Computational Geometry
TI - The extrinsic nature of the Hausdorff distance of optimal triangulations of manifolds
ER -
TY - JOUR
AB - In this paper we prove several new results around Gromov's waist theorem. We give a simple proof of Vaaler's theorem on sections of the unit cube using the Borsuk-Ulam-Crofton technique, consider waists of real and complex projective spaces, flat tori, convex bodies in Euclidean space; and establish waist-type results in terms of the Hausdorff measure.
AU - Akopyan, Arseniy
AU - Hubard, Alfredo
AU - Karasev, Roman
ID - 6634
IS - 2
JF - Topological Methods in Nonlinear Analysis
TI - Lower and upper bounds for the waists of different spaces
VL - 53
ER -
TY - CONF
AB - Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probability distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory
needed for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable the usage of existing computational topology software in this context.
AU - Edelsbrunner, Herbert
AU - Virk, Ziga
AU - Wagner, Hubert
ID - 6648
SN - 9783959771047
T2 - 35th International Symposium on Computational Geometry
TI - Topological data analysis in information space
VL - 129
ER -
TY - JOUR
AB - In this paper we discuss three results. The first two concern general sets of positive reach: we first characterize the reach of a closed set by means of a bound on the metric distortion between the distance measured in the ambient Euclidean space and the shortest path distance measured in the set. Secondly, we prove that the intersection of a ball with radius less than the reach with the set is geodesically convex, meaning that the shortest path between any two points in the intersection lies itself in the intersection. For our third result we focus on manifolds with positive reach and give a bound on the angle between tangent spaces at two different points in terms of the reach and the distance between the two points.
AU - Boissonnat, Jean-Daniel
AU - Lieutier, André
AU - Wintraecken, Mathijs
ID - 6671
IS - 1-2
JF - Journal of Applied and Computational Topology
SN - 2367-1726
TI - The reach, metric distortion, geodesic convexity and the variation of tangent spaces
VL - 3
ER -
TY - JOUR
AB - We study the topology generated by the temperature fluctuations of the cosmic microwave background (CMB) radiation, as quantified by the number of components and holes, formally given by the Betti numbers, in the growing excursion sets. We compare CMB maps observed by the Planck satellite with a thousand simulated maps generated according to the ΛCDM paradigm with Gaussian distributed fluctuations. The comparison is multi-scale, being performed on a sequence of degraded maps with mean pixel separation ranging from 0.05 to 7.33°. The survey of the CMB over 𝕊2 is incomplete due to obfuscation effects by bright point sources and other extended foreground objects like our own galaxy. To deal with such situations, where analysis in the presence of “masks” is of importance, we introduce the concept of relative homology. The parametric χ2-test shows differences between observations and simulations, yielding p-values at percent to less than permil levels roughly between 2 and 7°, with the difference in the number of components and holes peaking at more than 3σ sporadically at these scales. The highest observed deviation between the observations and simulations for b0 and b1 is approximately between 3σ and 4σ at scales of 3–7°. There are reports of mildly unusual behaviour of the Euler characteristic at 3.66° in the literature, computed from independent measurements of the CMB temperature fluctuations by Planck’s predecessor, the Wilkinson Microwave Anisotropy Probe (WMAP) satellite. The mildly anomalous behaviour of the Euler characteristic is phenomenologically related to the strongly anomalous behaviour of components and holes, or the zeroth and first Betti numbers, respectively. Further, since these topological descriptors show consistent anomalous behaviour over independent measurements of Planck and WMAP, instrumental and systematic errors may be an unlikely source. These are also the scales at which the observed maps exhibit low variance compared to the simulations, and approximately the range of scales at which the power spectrum exhibits a dip with respect to the theoretical model. Non-parametric tests show even stronger differences at almost all scales. Crucially, Gaussian simulations based on power-spectrum matching the characteristics of the observed dipped power spectrum are not able to resolve the anomaly. Understanding the origin of the anomalies in the CMB, whether cosmological in nature or arising due to late-time effects, is an extremely challenging task. Regardless, beyond the trivial possibility that this may still be a manifestation of an extreme Gaussian case, these observations, along with the super-horizon scales involved, may motivate the study of primordial non-Gaussianity. Alternative scenarios worth exploring may be models with non-trivial topology, including topological defect models.
AU - Pranav, Pratyush
AU - Adler, Robert J.
AU - Buchert, Thomas
AU - Edelsbrunner, Herbert
AU - Jones, Bernard J.T.
AU - Schwartzman, Armin
AU - Wagner, Hubert
AU - Van De Weygaert, Rien
ID - 6756
JF - Astronomy and Astrophysics
SN - 00046361
TI - Unexpected topology of the temperature fluctuations in the cosmic microwave background
VL - 627
ER -
TY - JOUR
AB - The Regge symmetry is a set of remarkable relations between two tetrahedra whose edge lengths are related in a simple fashion. It was first discovered as a consequence of an asymptotic formula in mathematical physics. Here, we give a simple geometric proof of Regge symmetries in Euclidean, spherical, and hyperbolic geometry.
AU - Akopyan, Arseniy
AU - Izmestiev, Ivan
ID - 6793
IS - 5
JF - Bulletin of the London Mathematical Society
SN - 00246093
TI - The Regge symmetry, confocal conics, and the Schläfli formula
VL - 51
ER -
TY - JOUR
AB - In this paper we construct a family of exact functors from the category of Whittaker modules of the simple complex Lie algebra of type to the category of finite-dimensional modules of the graded affine Hecke algebra of type . Using results of Backelin [2] and of Arakawa-Suzuki [1], we prove that these functors map standard modules to standard modules (or zero) and simple modules to simple modules (or zero). Moreover, we show that each simple module of the graded affine Hecke algebra appears as the image of a simple Whittaker module. Since the Whittaker category contains the BGG category as a full subcategory, our results generalize results of Arakawa-Suzuki [1], which in turn generalize Schur-Weyl duality between finite-dimensional representations of and representations of the symmetric group .
AU - Brown, Adam
ID - 6828
JF - Journal of Algebra
SN - 0021-8693
TI - Arakawa-Suzuki functors for Whittaker modules
VL - 538
ER -
TY - CONF
AB - When can a polyomino piece of paper be folded into a unit cube? Prior work studied tree-like polyominoes, but polyominoes with holes remain an intriguing open problem. We present sufficient conditions for a polyomino with hole(s) to fold into a cube, and conditions under which cube folding is impossible. In particular, we show that all but five special simple holes guarantee foldability.
AU - Aichholzer, Oswin
AU - Akitaya, Hugo A
AU - Cheung, Kenneth C
AU - Demaine, Erik D
AU - Demaine, Martin L
AU - Fekete, Sandor P
AU - Kleist, Linda
AU - Kostitsyna, Irina
AU - Löffler, Maarten
AU - Masárová, Zuzana
AU - Mundilova, Klara
AU - Schmidt, Christiane
ID - 6989
T2 - Proceedings of the 31st Canadian Conference on Computational Geometry
TI - Folding polyominoes with holes into a cube
ER -
TY - THES
AB - We describe arrangements of three-dimensional spheres from a geometrical and topological point of view. Real data (fitting this setup) often consist of soft spheres which show certain degree of deformation while strongly packing against each other. In this context, we answer the following questions: If we model a soft packing of spheres by hard spheres that are allowed to overlap, can we measure the volume in the overlapped areas? Can we be more specific about the overlap volume, i.e. quantify how much volume is there covered exactly twice, three times, or k times? What would be a good optimization criteria that rule the arrangement of soft spheres while making a good use of the available space? Fixing a particular criterion, what would be the optimal sphere configuration? The first result of this thesis are short formulas for the computation of volumes covered by at least k of the balls. The formulas exploit information contained in the order-k Voronoi diagrams and its closely related Level-k complex. The used complexes lead to a natural generalization into poset diagrams, a theoretical formalism that contains the order-k and degree-k diagrams as special cases. In parallel, we define different criteria to determine what could be considered an optimal arrangement from a geometrical point of view. Fixing a criterion, we find optimal soft packing configurations in 2D and 3D where the ball centers lie on a lattice. As a last step, we use tools from computational topology on real physical data, to show the potentials of higher-order diagrams in the description of melting crystals. The results of the experiments leaves us with an open window to apply the theories developed in this thesis in real applications.
AU - Iglesias Ham, Mabel
ID - 201
TI - Multiple covers with balls
ER -
TY - GEN
AB - We prove that any convex body in the plane can be partitioned into m convex parts of equal areas and perimeters for any integer m≥2; this result was previously known for prime powers m=pk. We also give a higher-dimensional generalization.
AU - Akopyan, Arseniy
AU - Avvakumov, Sergey
AU - Karasev, Roman
ID - 75
TI - Convex fair partitions into arbitrary number of pieces
ER -
TY - JOUR
AB - We give a simple proof of T. Stehling's result [4], whereby in any normal tiling of the plane with convex polygons with number of sides not less than six, all tiles except a finite number are hexagons.
AU - Akopyan, Arseniy
ID - 409
IS - 4
JF - Comptes Rendus Mathematique
SN - 1631073X
TI - On the number of non-hexagons in a planar tiling
VL - 356
ER -
TY - JOUR
AB - We consider congruences of straight lines in a plane with the combinatorics of the square grid, with all elementary quadrilaterals possessing an incircle. It is shown that all the vertices of such nets (we call them incircular or IC-nets) lie on confocal conics. Our main new results are on checkerboard IC-nets in the plane. These are congruences of straight lines in the plane with the combinatorics of the square grid, combinatorially colored as a checkerboard, such that all black coordinate quadrilaterals possess inscribed circles. We show how this larger class of IC-nets appears quite naturally in Laguerre geometry of oriented planes and spheres and leads to new remarkable incidence theorems. Most of our results are valid in hyperbolic and spherical geometries as well. We present also generalizations in spaces of higher dimension, called checkerboard IS-nets. The construction of these nets is based on a new 9 inspheres incidence theorem.
AU - Akopyan, Arseniy
AU - Bobenko, Alexander
ID - 458
IS - 4
JF - Transactions of the American Mathematical Society
TI - Incircular nets and confocal conics
VL - 370
ER -
TY - JOUR
AB - Inclusion–exclusion is an effective method for computing the volume of a union of measurable sets. We extend it to multiple coverings, proving short inclusion–exclusion formulas for the subset of Rn covered by at least k balls in a finite set. We implement two of the formulas in dimension n=3 and report on results obtained with our software.
AU - Edelsbrunner, Herbert
AU - Iglesias Ham, Mabel
ID - 530
JF - Computational Geometry: Theory and Applications
TI - Multiple covers with balls I: Inclusion–exclusion
VL - 68
ER -
TY - JOUR
AB - Inside a two-dimensional region (``cake""), there are m nonoverlapping tiles of a certain kind (``toppings""). We want to expand the toppings while keeping them nonoverlapping, and possibly add some blank pieces of the same ``certain kind,"" such that the entire cake is covered. How many blanks must we add? We study this question in several cases: (1) The cake and toppings are general polygons. (2) The cake and toppings are convex figures. (3) The cake and toppings are axis-parallel rectangles. (4) The cake is an axis-parallel rectilinear polygon and the toppings are axis-parallel rectangles. In all four cases, we provide tight bounds on the number of blanks.
AU - Akopyan, Arseniy
AU - Segal Halevi, Erel
ID - 58
IS - 3
JF - SIAM Journal on Discrete Mathematics
TI - Counting blanks in polygonal arrangements
VL - 32
ER -
TY - JOUR
AB - We prove that any cyclic quadrilateral can be inscribed in any closed convex C1-curve. The smoothness condition is not required if the quadrilateral is a rectangle.
AU - Akopyan, Arseniy
AU - Avvakumov, Sergey
ID - 6355
JF - Forum of Mathematics, Sigma
SN - 2050-5094
TI - Any cyclic quadrilateral can be inscribed in any closed convex smooth curve
VL - 6
ER -