The of a set of points with respect to a convex body equals the minimum value of such that a translate of contains . Each choice of gives a different function on the set of bounded subsets of ; we characterize which functions can arise in this way. Our characterization draws on the theory of , a recently introduced generalization of metrics from functions on pairs to functions on finite subsets. We additionally investigate functions which arise by restricting the generalized circumradius to a finite subset of . We obtain elegant characterizations in the case that is a simplex or parallelotope.

We construct an example of a group for a finite abelian group , a subset of , and two finite subsets of , such that it is undecidable in ZFC whether can be tiled by translations of . In particular, this implies that this tiling problem is , in the sense that (in the standard universe of ZFC) there exist translational tilings of by the tiles , but no periodic tilings. Previously, such aperiodic or undecidable translational tilings were only constructed for sets of eleven or more tiles (mostly in ). A similar construction also applies for for sufficiently large . If one allows the group to be non-abelian, a variant of the construction produces an undecidable translational tiling with only one tile . The argument proceeds by first observing that a single tiling equation is able to encode an arbitrary system of tiling equations, which in turn can encode an arbitrary system of certain functional equations once one has two or more tiles. In particular, one can use two tiles to encode tiling problems for an arbitrary number of tiles.

Let be a set of in the plane, so that every site has an . Let be the defined by , i.e., the graph with vertex set and an edge between two distinct sites if and only if the disks with centers , and radii , intersect. Our goal is to design data structures that maintain the connectivity structure of as sites are inserted and/or deleted in . First, we consider , i.e., we fix , for all sites . For this case, we describe a data structure that has amortized update time and query time. Second, we look at disk graphs , i.e., for all , we have , for a parameter that is known in advance. Here, we not only investigate the fully dynamic case, but also the incremental and the decremental scenario, where only insertions or only deletions of sites are allowed. In the fully dynamic case, we achieve amortized expected update time and query time . This improves the currently best update time by a factor of . In the incremental case, we achieve logarithmic dependency on , with a data structure that has amortized query time and amortized expected update time, where denotes the inverse Ackermann function. For the decremental setting, we first develop an efficient decremental data structure: given two sets and of disks in the plane, we can delete disks from , and upon each deletion, we receive a list of all disks in that no longer intersect the union of . Using this data structure, we get decremental data structures with a query time of that supports deletions in overall expected time for disk graphs with bounded radius ratio and overall expected time for disk graphs with arbitrary radii, assuming that the deletion sequence is oblivious of the internal random choices of the data structures.

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 planar diagrams, whereas their exteriors, which are compact 3-manifolds with torus boundary, are encoded by triangulations. Here, we give the first practical algorithm for finding a diagram of a knot given a triangulation of its exterior. Our method applies to links as well as knots, and allows us to recover links with hundreds of crossings. We use it to find the first diagrams known for 23 principal congruence arithmetic link exteriors; the largest has over 2500 crossings. Other applications include finding pairs of knots with the same 0-surgery, which relates to questions about slice knots and the smooth 4D Poincaré conjecture.

Exhibiting a deep connection between purely geometric problems and real algebra, the complexity class plays a crucial role in the study of geometric problems. Sometimes is referred to as the 'real analog' of NP. While NP is a class of computational problems that deals with existentially quantified variables, deals with existentially quantified variables. In analogy to and in the famous polynomial hierarchy, we study the complexity classes and with variables. Our main interest is the Area Universality problem, where we are given a plane graph , and ask if for each assignment of areas to the inner faces of , there exists a straight-line drawing of realizing the assigned areas. We conjecture that Area Universality is -complete and support this conjecture by proving - and -completeness of two variants of Area Universality. To this end, we introduce tools to prove -hardness and membership. Finally, we present geometric problems as candidates for -complete problems. These problems have connections to the concepts of imprecision, robustness, and extendability.

Let and . Given a set of points in the plane, a pair of points in is called -, if there are at least points from strictly on each side of the line spanned by and . A - is a subset of with all its pairs -. We show that if is in general position (i.e., no three points on a line), there is a -deep clique of size at least ; this is tight, for example in convex position. A -deep clique in any set of points cannot have size exceeding ; this is tight for . Moreover, for , a -deep clique cannot have size exceeding ; this is tight within a constant factor. We also pay special attention to -deep cliques (for even), which are called . These have been considered in the literature by Khovanova and Yang, 2012, and they play a role in the latter bound above. Every set in general position with a halving clique of size must have at least points. If is in convex position, the set must have size at least . This is tight, i.e., there are sets of points in convex position which can be extended to a set of points where is a halving clique. Interestingly, this is not the case for all sets in convex position (even if parallel connecting lines among point pairs in are excluded).

This paper studies the discrete differential geometry of the checkerboard pattern inscribed in a quadrilateral net by connecting edge midpoints. It turns out to be a versatile tool which allows us to consistently define principal nets, Koenigs nets and eventually isothermic nets as a combination of both. Principal nets are based on the notions of orthogonality and conjugacy and can be identified with sphere congruences that are entities of Möbius geometry. Discrete Koenigs nets are defined via the existence of the so-called conic of Koenigs. We find several interesting properties of Koenigs nets, including their being dualizable and having equal Laplace invariants. Isothermic nets can be defined as Koenigs nets that are also principal nets. We prove that the class of isothermic nets is invariant under both dualization and Möbius transformations. Among other things, this allows a natural construction of discrete minimal surfaces and their Goursat transformations.

We say that a set of points is an -nearly -distance set if there exist , such that the distance between any two distinct points in falls into . In this paper, we study the quantity and its relation to the classical quantity : the size of the largest -distance set in . We obtain that for , as well as for any fixed , provided that is sufficiently large. The last result answers a question, proposed by Erdős, Makai, and Pach. We also address a closely related Turán-type problem, studied by Erdős, Makai, Pach, and Spencer in the 90s: given points in , how many pairs of them form a distance that belongs to , where are fixed and any two points in the set are at distance at least 1 apart? We establish the connection between this quantity and a quantity closely related to , as well as obtain an exact answer for the same ranges ,  as above.

We study the behavior at infinity of the farthest and the higher-order Voronoi diagram of  line segments or lines in a -dimensional Euclidean space. The unbounded parts of these diagrams can be encoded by a on the sphere of directions  . We show that the combinatorial complexity of the Gaussian map for the order- Voronoi diagram of  line segments and lines is , which is tight for . This exactly reflects the combinatorial complexity of the unbounded features of these diagrams. All the -dimensional cells of the farthest Voronoi diagram are unbounded, its -skeleton is connected, and it does not have tunnels. A -cell of the Voronoi diagram is called a tunnel if the set of its unbounded directions, represented as points on its Gaussian map, is not connected. In a three-dimensional space, the farthest Voronoi diagram of   lines in general position has exactly three-dimensional cells. The Gaussian map of the farthest Voronoi diagram of line segments and lines can be constructed in time, for , while if , the time drops to worst-case optimal  . We extend the obtained results to bounded polyhedra and clusters of points as sites.

A recent generalization of the Erdős Unit Distance Problem, proposed by Palsson, Senger, and Sheffer, asks for the maximum number of unit distance paths with a given number of vertices in the plane and in 3-space. Studying a variant of this question, we prove sharp bounds on the number of unit distance paths and cycles on the sphere of radius . We also consider a similar problem about 3-regular unit distance graphs in  .

Given positive integers and a finite field , a set is (, )- if every -dimensional affine subspace contains at most elements of . By a simple averaging argument, the maximum size of a (, )-subspace evasive set is at most . When and are fixed, and is sufficiently large, the matching lower bound is proved by Dvir and Lovett. We provide an alternative proof of this result using the random algebraic method. We also prove sharp upper bounds on the size of (, )-evasive sets in case is large, extending results of Ben-Aroya and Shinkar. The existence of optimal evasive sets has several interesting consequences in combinatorial geometry. We show that the minimum number of -dimensional linear hyperplanes needed to cover the grid is , which matches the upper bound proved by Balko et al., and settles a problem proposed by Brass et al. Furthermore, we improve the best known lower bound on the maximum number of incidences between points and hyperplanes in assuming their incidence graph avoids the complete bipartite graph for some large constant .

An arc in is a set such that no three points of are collinear. We use the method of hypergraph containers to prove several counting results for arcs. Let denote the family of all arcs in . Our main result is the bound This matches, up to the factor hidden in the (1) notation, the trivial lower bound that comes from considering all subsets of an arc of size . We also give upper bounds for the number of arcs of a fixed (large) size. Let , and let denote the family of all arcs in with cardinality . We prove that This result improves a bound of Roche-Newton and Warren [12]. A nearly matching lower bound follows by considering all subsets of size of an arc of size .

The problem of packing of equal disks (or circles) into a rectangle is a fundamental geometric problem. (By a packing here we mean an arrangement of disks in a rectangle without overlapping.) We consider the following algorithmic generalization of the equal disk packing problem. In this problem, for a given packing of equal disks into a rectangle, the question is whether by changing positions of a small number of disks, we can allocate space for packing more disks. More formally, in the repacking problem, for a given set of equal disks packed into a rectangle and integers and , we ask whether it is possible by changing positions of at most disks to pack disks. Thus the problem of packing equal disks is the special case of our problem with . While the computational complexity of packing equal disks into a rectangle remains open, we prove that the repacking problem is NP-hard already for . Our main algorithmic contribution is an algorithm that solves the repacking problem in time , where || is the input size. That is, the problem is fixed-parameter tractable parameterized by and .

We present an algorithm that, given finite diagrams of simplicial sets , , , i.e., functors , such that (, ) is a cellular pair, , , computes the set of homotopy classes of maps of diagrams extending a given . For fixed , the running time of the algorithm is polynomial. When the stability condition is dropped, the problem is known to be undecidable. Using Elmendorf's theorem, we deduce an algorithm that, given finite simplicial sets , ,  with an action of a finite group , computes the set of homotopy classes of equivariant maps extending a given equivariant map under the stability assumption and , for all subgroups . Again, for fixed , the algorithm runs in polynomial time. We further apply our results to Tverberg-type problem in computational topology: Given a -dimensional simplicial complex , is there a map without -tuple intersection points? In the metastable range of dimensions, , the problem is shown algorithmically decidable in polynomial time when , , and  are fixed.

A well-known open problem of Meir and Moser asks if the squares of sidelength 1/ for can be packed perfectly into a rectangle of area . In this paper we show that for any , and any that is sufficiently large depending on , the squares of sidelength for can be packed perfectly into a square of area . This was previously known (if one packs a rectangle instead of a square) for (in which case one can take ).

Let be an intersection graph of geometric objects in the plane. We show that a maximum matching in can be found in time with high probability, where is the density of the geometric objects and is a constant such that matrices can be multiplied in time. The same result holds for any subgraph of , as long as a geometric representation is at hand. For this, we combine algebraic methods, namely computing the rank of a matrix via Gaussian elimination, with the fact that geometric intersection graphs have small separators. We also show that in many interesting cases, the maximum matching problem in a general geometric intersection graph can be reduced to the case of bounded density. In particular, a maximum matching in the intersection graph of any family of translates of a convex object in the plane can be found in time with high probability, and a maximum matching in the intersection graph of a family of planar disks with radii in can be found in time with high probability.

Ball's complex plank theorem states that if are unit vectors in , and are non-negative numbers satisfying , then there exists a unit vector in for which for every . Here we present a streamlined version of Ball's original proof.

Given a finite set , let denote the set of all points within distance to at least points of . Allowing and to vary, we obtain a 2-parameter family of spaces that grow larger when increases or decreases, called the . Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a Čech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.

Simple drawings are drawings of graphs in which the edges are Jordan arcs and each pair of edges share at most one point (a proper crossing or a common endpoint). A simple drawing is c-monotone if there is a point  such that each ray emanating from  crosses each edge of the drawing at most once. We introduce a special kind of c-monotone drawings that we call generalized twisted drawings. A c-monotone drawing is generalized twisted if there is a ray emanating from  that crosses all the edges of the drawing. Via this class of drawings, we show that every simple drawing of the complete graph with  vertices contains  pairwise disjoint edges and a plane cycle (and hence path) of length . Both results improve over best previously published lower bounds. On the way we show several structural results and properties of generalized twisted and c-monotone drawings, some of which we believe to be of independent interest. For example, we show that a drawing is c-monotone if there exists a point such that no edge of is crossed more than once by any ray that emanates from and passes through a vertex of .

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 cell corresponding to the singularity. We divide polyhedral surfaces into discrete conformal classes using a generalization of discrete conformal equivalence pioneered by Feng Luo. We subsequently show that, in every discrete conformal class, there exists a polyhedral surface with constant discrete Gaussian curvature. We also provide explicit examples to demonstrate that this surface is in general not unique.

For a locally finite set in , the order- Brillouin tessellations form an infinite sequence of convex face-to-face tilings of the plane. If the set is coarsely dense and generic, then the corresponding infinite sequences of minimum and maximum angles are both monotonic in . As an example, a stationary Poisson point process in is locally finite, coarsely dense, and generic with probability one. For such a set, the distributions of angles in the Voronoi tessellations, Delaunay mosaics, and Brillouin tessellations are independent of the order and can be derived from the formula for angles in order-1 Delaunay mosaics given by Miles (Math. Biosci. , 85-127 (1970)).