Nathan M Dunfield,Malik Obeidin,Cameron Gates Rudd
Nathan M Dunfield
A knot is a circle piecewise-linearly embedded into the 3-sphere. The topology of a knot is intimately related to that of its exterior, which is the complement of an open regular neighborhood of the knot. Knots are typically encoded by plan...
David Bryant,Katharina T Huber,Vincent Moulton et al.
David Bryant et al.
The generalized circumradius of a set of points A⊆Rd with respect to a convex body K equals the minimum value of λ≥0 such that a translate of λK contains A. Each choice of K gives a different function on the set of bou...
Undecidable Translational Tilings with Only Two Tiles, or One Nonabelian Tile [0.03%]
仅用两块砖或一个非交换砖的不可判定平铺问题
Rachel Greenfeld,Terence Tao
Rachel Greenfeld
We construct an example of a group G=Z2×G0 for a finite abelian group G0, a subset E of G0, and two finite subsets F1,F2 of G, such that it is undecidable in ZFC whether Z2×E can be tiled by translations of F1,F2. In particular, t...
Marek Filakovský,Lukáš Vokřínek
Marek Filakovský
We present an algorithm that, given finite diagrams of simplicial sets X, A, Y, i.e., functors Iop→sSet, such that (X, A) is a cellular pair, dimX≤2·connY, connY≥1, computes the set [X,Y]A of homotopy classes of maps ...
Édouard Bonnet,Sergio Cabello,Wolfgang Mulzer
Édouard Bonnet
Let G be an intersection graph of n geometric objects in the plane. We show that a maximum matching in G can be found in O(ρ3ω/2nω/2) time with high probability, where ρ is the density of the geometric objects and ω...
Nearly k-Distance Sets [0.03%]
接近k-距离集
Nóra Frankl,Andrey Kupavskii
Nóra Frankl
We say that a set of points S⊂Rd is an ε-nearly k-distance set if there exist 1≤t1≤…≤tk, such that the distance between any two distinct points in S falls into [t1,t1+ε]∪⋯∪[tk,tk+	...
René Corbet,Michael Kerber,Michael Lesnick et al.
René Corbet et al.
Given a finite set A⊂Rd, let Covr,k denote the set of all points within distance r to at least k points of A. Allowing r and k to vary, we obtain a 2-parameter family of spaces that grow larger when r increases or k decreases, called ...
Completeness for the Complexity Class [Formula: see text] and Area-Universality [0.03%]
[公式：请参见原文]的完备性及面积普遍性
Michael Gene Dobbins,Linda Kleist,Tillmann Miltzow et al.
Michael Gene Dobbins et al.
Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class ∃R plays a crucial role in the study of geometric problems. Sometimes ∃R is referred to as the 'real analog' of NP. While NP i...
Hana Dal Poz Kouřimská
Hana Dal Poz Kouřimská
We study a new discretization of the Gaussian curvature for polyhedral surfaces. This discrete Gaussian curvature is defined on each conical singularity of a polyhedral surface as the quotient of the angle defect and the area of the Voronoi...
Deletion in Abstract Voronoi Diagrams in Expected Linear Time and Related Problems [0.03%]
期望线性时间内抽象Voronoi图的删除及有关问题研究
Kolja Junginger,Evanthia Papadopoulou
Kolja Junginger
Updating an abstract Voronoi diagram in linear time, after deletion of one site, has been an open problem in a long time; similarly, for any concrete Voronoi diagram of generalized (non-point) sites. In this paper we present a simple, expec...