@article{9317,
  abstract     = {Given a locally finite X⊆Rd and a radius r≥0, the k-fold cover of X and r consists of all points in Rd that have k or more points of X within distance r. We consider two filtrations—one in scale obtained by fixing k and increasing r, and the other in depth obtained by fixing r and decreasing k—and we compute the persistence diagrams of both. While standard methods suffice for the filtration in scale, we need novel geometric and topological concepts for the filtration in depth. In particular, we introduce a rhomboid tiling in Rd+1 whose horizontal integer slices are the order-k Delaunay mosaics of X, and construct a zigzag module of Delaunay mosaics that is isomorphic to the persistence module of the multi-covers.},
  author       = {Edelsbrunner, Herbert and Osang, Georg F},
  issn         = {1432-0444},
  journal      = {Discrete and Computational Geometry},
  pages        = {1296–1313},
  publisher    = {Springer Nature},
  title        = {{The multi-cover persistence of Euclidean balls}},
  doi          = {10.1007/s00454-021-00281-9},
  volume       = {65},
  year         = {2021},
}

@article{5986,
  abstract     = {Given a triangulation of a point set in the plane, a flip deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge. It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips, but we characterize when this is possible. There is an obvious necessary condition: for each label l, if edge e has label l in the first triangulation and edge f has label l in the second triangulation, then there must be some sequence of flips that moves label l from e to f, ignoring all other labels. Bose, Lubiw, Pathak and Verdonschot formulated the Orbit Conjecture, which states that this necessary condition is also sufficient, i.e. that all labels can be simultaneously mapped to their destination if and only if each label individually can be mapped to its destination. We prove this conjecture. Furthermore, we give a polynomial-time algorithm (with 𝑂(𝑛8) being a crude bound on the run-time) to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of 𝑂(𝑛7) on the length of the flip sequence. Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the flip complex, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.},
  author       = {Lubiw, Anna and Masárová, Zuzana and Wagner, Uli},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {4},
  pages        = {880--898},
  publisher    = {Springer Nature},
  title        = {{A proof of the orbit conjecture for flipping edge-labelled triangulations}},
  doi          = {10.1007/s00454-018-0035-8},
  volume       = {61},
  year         = {2019},
}

@article{1064,
  abstract     = {In 1945, A.W. Goodman and R.E. Goodman proved the following conjecture by P. Erdős: Given a family of (round) disks of radii r1, … , rn in the plane, it is always possible to cover them by a disk of radius R= ∑ ri, provided they cannot be separated into two subfamilies by a straight line disjoint from the disks. In this note we show that essentially the same idea may work for different analogues and generalizations of their result. In particular, we prove the following: Given a family of positive homothetic copies of a fixed convex body K⊂ Rd with homothety coefficients τ1, … , τn> 0 , it is always possible to cover them by a translate of d+12(∑τi)K, provided they cannot be separated into two subfamilies by a hyperplane disjoint from the homothets.},
  author       = {Akopyan, Arseniy and Balitskiy, Alexey and Grigorev, Mikhail},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {4},
  pages        = {1001--1009},
  publisher    = {Springer},
  title        = {{On the circle covering theorem by A.W. Goodman and R.E. Goodman}},
  doi          = {10.1007/s00454-017-9883-x},
  volume       = {59},
  year         = {2018},
}

@article{22198,
  abstract     = {Packings of equal disks in the plane are known to have density at most
π/
√
12, although this density is never achieved in the square torus, which is what we
call the plane modulo the square lattice. We find packings of disks in a square torus
that we conjecture to be the most dense for certain numbers of packing disks, using
continued fractions to approximate 1/
√
3 and 2 −
√
3. We also define a constant to
measure the efficiency of a packing motived by a related constant due to Markov for
continued fractions. One idea is to use the unique factorization property of Gaussian
integers to prove that there is an upper bound for the Markov constant for grid-like
packings. By way of contrast, we show that an upper bound by Gruber [In many cases
optimal configurations are almost regular hexagonal, vol. 65, pp. 121–145, 1999;Geom
Dedicata 84(1–3):271–320, 2001] for the error for the limiting density of a packing
of equal disks in a planar square, which is on the order of 1/
√
N, is the best possible,
whereas for our examples for the square torus, the error for the limiting density is on
the order of 1/N, where N is the number of packing disks.},
  author       = {Connelly, Robert and Funkhouser, Matthew and Kuperberg, Vivian Zieve and Solomonides, Evan},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {3},
  pages        = {614--642},
  publisher    = {Springer Nature},
  title        = {{Packings of equal disks in a square torus}},
  doi          = {10.1007/s00454-016-9843-x},
  volume       = {58},
  year         = {2017},
}

@article{2815,
  abstract     = {The fact that a sum of isotropic Gaussian kernels can have more modes than kernels is surprising. Extra (ghost) modes do not exist in ℝ1 and are generally not well studied in higher dimensions. We study a configuration of n+1 Gaussian kernels for which there are exactly n+2 modes. We show that all modes lie on a finite set of lines, which we call axes, and study the restriction of the Gaussian mixture to these axes in order to discover that there are an exponential number of critical points in this configuration. Although the existence of ghost modes remained unknown due to the difficulty of finding examples in ℝ2, we show that the resilience of ghost modes grows like the square root of the dimension. In addition, we exhibit finite configurations of isotropic Gaussian kernels with superlinearly many modes.},
  author       = {Edelsbrunner, Herbert and Fasy, Brittany Terese and Rote, Günter},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {4},
  pages        = {797 -- 822},
  publisher    = {Springer},
  title        = {{Add isotropic Gaussian kernels at own risk: More and more resilient modes in higher dimensions}},
  doi          = {10.1007/s00454-013-9517-x},
  volume       = {49},
  year         = {2013},
}

@article{3993,
  abstract     = {We present algorithms for constructing a hierarchy of increasingly coarse Morse-Smale complexes that decompose a piecewise linear 2-manifold. While these complexes are defined only in the smooth category, we extend the construction to the piecewise linearcategory by ensuring structural integrity and simulating differentiability. We then simplify Morse-Smale complexes by canceling pairs of critical points in order of increasing persistence.},
  author       = {Edelsbrunner, Herbert and Harer, John and Zomorodian, Afra},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  pages        = {87 -- 107},
  publisher    = {Springer nature},
  title        = {{Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds}},
  doi          = {10.1007/s00454-003-2926-5},
  volume       = {30},
  year         = {2003},
}

@article{4061,
  abstract     = {We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of N points in Ed in time O(Fd (N,N) logd N), where Fd (n,m) is the time required to compute a bichromatic closest pair among n red and m green points in Ed . If Fd (N,N)=Ω(N1+ε), for some fixed e{open}>0, then the running time improves to O(Fd (N,N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected time O((nm log n log m)2/3+m log2 n+n log2 m) in E3, which yields an O(N4/3 log4/3 N) expected time, algorithm for computing a Euclidean minimum spanning tree of N points in E3. In d≥4 dimensions we obtain expected time O((nm)1-1/([d/2]+1)+ε+m log n+n log m) for the bichromatic closest pair problem and O(N2-2/([d/2]+1)ε) for the Euclidean minimum spanning tree problem, for any positive e{open}.},
  author       = {Agarwal, Pankaj and Edelsbrunner, Herbert and Schwarzkopf, Otfried and Welzl, Emo},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {407 -- 422},
  publisher    = {Springer},
  title        = {{Euclidean minimum spanning trees and bichromatic closest pairs}},
  doi          = {10.1007/BF02574698},
  volume       = {6},
  year         = {1991},
}

@article{4062,
  abstract     = {We prove that for any set S of n points in the plane and n3-α triangles spanned by the points in S there exists a point (not necessarily in S) contained in at least n3-3α/(c log5 n) of the triangles. This implies that any set of n points in three-dimensional space defines at most {Mathematical expression} halving planes.},
  author       = {Aronov, Boris and Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha and Wenger, Rephael},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {435 -- 442},
  publisher    = {Springer},
  title        = {{Points and triangles in the plane and halving planes in space}},
  doi          = {10.1007/BF02574700},
  volume       = {6},
  year         = {1991},
}

@article{4066,
  abstract     = {We consider several problems involving points and planes in three dimensions. Our main results are: (i) The maximum number of faces boundingm distinct cells in an arrangement ofn planes isO(m 2/3 n logn +n 2); we can calculatem such cells specified by a point in each, in worst-case timeO(m 2/3 n log3 n+n 2 logn). (ii) The maximum number of incidences betweenn planes andm vertices of their arrangement isO(m 2/3 n logn+n 2), but this number is onlyO(m 3/5– n 4/5+2 +m+n logm), for any>0, for any collection of points no three of which are collinear. (iii) For an arbitrary collection ofm points, we can calculate the number of incidences between them andn planes by a randomized algorithm whose expected time complexity isO((m 3/4– n 3/4+3 +m) log2 n+n logn logm) for any>0. (iv) Givenm points andn planes, we can find the plane lying immediately below each point in randomized expected timeO([m 3/4– n 3/4+3 +m] log2 n+n logn logm) for any>0. (v) The maximum number of facets (i.e., (d–1)-dimensional faces) boundingm distinct cells in an arrangement ofn hyperplanes ind dimensions,d>3, isO(m 2/3 n d/3 logn+n d–1). This is also an upper bound for the number of incidences betweenn hyperplanes ind dimensions andm vertices of their arrangement. The combinatorial bounds in (i) and (v) and the general bound in (ii) are almost tight.},
  author       = {Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {197 -- 216},
  publisher    = {Springer},
  title        = {{The complexity of many cells in arrangements of planes and related problems}},
  doi          = {10.1007/BF02187785},
  volume       = {5},
  year         = {1990},
}

@article{4068,
  abstract     = {LetS be a collection ofn convex, closed, and pairwise nonintersecting sets in the Euclidean plane labeled from 1 ton. A pair of permutations
(i1i2in−1in)(inin−1i2i1) 
is called ageometric permutation of S if there is a line that intersects all sets ofS in this order. We prove thatS can realize at most 2n–2 geometric permutations. This upper bound is tight.},
  author       = {Edelsbrunner, Herbert and Sharir, Micha},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {35 -- 42},
  publisher    = {Springer},
  title        = {{The maximum number of ways to stabn convex nonintersecting sets in the plane is 2n−2}},
  doi          = {10.1007/BF02187778},
  volume       = {5},
  year         = {1990},
}

@article{4072,
  abstract     = {We show that the total number of edges ofm faces of an arrangement ofn lines in the plane isO(m 2/3– n 2/3+2 +n) for any>0. The proof takes an algorithmic approach, that is, we describe an algorithm for the calculation of thesem faces and derive the upper bound from the analysis of the algorithm. The algorithm uses randomization and its expected time complexity isO(m 2/3– n 2/3+2 logn+n logn logm). If instead of lines we have an arrangement ofn line segments, then the maximum number of edges ofm faces isO(m 2/3– n 2/3+2 +n (n) logm) for any>0, where(n) is the functional inverse of Ackermann's function. We give a (randomized) algorithm that produces these faces and takes expected timeO(m 2/3– n 2/3+2 log+n(n) log2 n logm).},
  author       = {Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {161 -- 196},
  publisher    = {Springer},
  title        = {{The complexity and construction of many faces in arrangements of lines and of segments}},
  doi          = {10.1007/BF02187784},
  volume       = {5},
  year         = {1990},
}

@article{4074,
  abstract     = {We present upper and lower bounds for extremal problems defined for arrangements of lines, circles, spheres, and alike. For example, we prove that the maximum number of edges boundingm cells in an arrangement ofn lines is Θ(m 2/3 n 2/3 +n), and that it isO(m 2/3 n 2/3 β(n) +n) forn unit-circles, whereβ(n) (and laterβ(m, n)) is a function that depends on the inverse of Ackermann's function and grows extremely slowly. If we replace unit-circles by circles of arbitrary radii the upper bound goes up toO(m 3/5 n 4/5 β(n) +n). The same bounds (without theβ(n)-terms) hold for the maximum sum of degrees ofm vertices. In the case of vertex degrees in arrangements of lines and of unit-circles our bounds match previous results, but our proofs are considerably simpler than the previous ones. The maximum sum of degrees ofm vertices in an arrangement ofn spheres in three dimensions isO(m 4/7 n 9/7 β(m, n) +n 2), in general, andO(m 3/4 n 3/4 β(m, n) +n) if no three spheres intersect in a common circle. The latter bound implies that the maximum number of unit-distances amongm points in three dimensions isO(m 3/2 β(m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given.},
  author       = {Clarkson, Kenneth and Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha and Welzl, Emo},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {99 -- 160},
  publisher    = {Springer},
  title        = {{Combinatorial complexity bounds for arrangements of curves and spheres}},
  doi          = {10.1007/BF02187783},
  volume       = {5},
  year         = {1990},
}

@article{4081,
  abstract     = {This paper studies applications of envelopes of piecewise linear functions to problems in computational geometry. Among these applications we find problems involving hidden line/surface elimination, motion planning, transversals of polytopes, and a new type of Voronoi diagram for clusters of points. All results are either combinatorial or computational in nature. They are based on the combinatorial analysis in two companion papers [PS] and [E2] and a divide-and-conquer algorithm for computing envelopes described in this paper.},
  author       = {Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {311 -- 336},
  publisher    = {Springer},
  title        = {{The upper envelope of piecewise linear functions: Algorithms and applications}},
  doi          = {10.1007/BF02187733},
  volume       = {4},
  year         = {1989},
}

@article{4086,
  abstract     = {This note proves that the maximum number of faces (of any dimension) of the upper envelope of a set ofn possibly intersectingd-simplices ind+1 dimensions is (n d (n)). This is an extension of a result of Pach and Sharir [PS] who prove the same bound for the number ofd-dimensional faces of the upper envelope.},
  author       = {Edelsbrunner, Herbert},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {4},
  pages        = {337 -- 343},
  publisher    = {Springer},
  title        = {{The upper envelope of piecewise linear functions: Tight bounds on the number of faces }},
  doi          = {10.1007/BF02187734},
  volume       = {4},
  year         = {1989},
}

@article{4088,
  abstract     = {Anarrangement ofn lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists ofO(n 2) regions, calledfaces. In this paper we study the problem of calculating and storing arrangementsimplicitly, using subquadratic space and preprocessing, so that, given any query pointp, we can calculate efficiently the face containingp. First, we consider the case of lines and show that with (n) space1 and (n 3/2) preprocessing time, we can answer face queries in (n)+O(K) time, whereK is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: (1) given a set ofn points, find a straight-edge spanning tree of these points such that any line intersects only a few edges of the tree, (2) given a simple polygonal path , form a data structure from which we can find the convex hull of any subpath of quickly, and (3) given a set of points, organize them so that the convex hull of their subset lying above a query line can be found quickly. Second, using random sampling, we give a tradeoff between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in (n 1/3)+O(K) time, given(n 4/3) space and (n 5/3) preprocessing time. Lastly, we note that our techniques allow us to computem faces in an arrangement ofn lines in time (m 2/3 n 2/3+n), which is nearly optimal.},
  author       = {Edelsbrunner, Herbert and Guibas, Leonidas and Hershberger, John and Seidel, Raimund and Sharir, Micha and Snoeyink, Jack and Welzl, Emo},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {433 -- 466},
  publisher    = {Springer},
  title        = {{Implicitly representing arrangements of lines or segments}},
  doi          = {10.1007/BF02187742},
  volume       = {4},
  year         = {1989},
}

@article{4089,
  abstract     = {Motivated by a number of motion-planning questions, we investigate in this paper some general topological and combinatorial properties of the boundary of the union ofn regions bounded by Jordan curves in the plane. We show that, under some fairly weak conditions, a simply connected surface can be constructed that exactly covers this union and whose boundary has combinatorial complexity that is nearly linear, even though the covered region can have quadratic complexity. In the case where our regions are delimited by Jordan acrs in the upper halfplane starting and ending on thex-axis such that any pair of arcs intersect in at most three points, we prove that the total number of subarcs that appear on the boundary of the union is only (n(n)), where(n) is the extremely slowly growing functional inverse of Ackermann's function.},
  author       = {Edelsbrunner, Herbert and Guibas, Leonidas and Hershberger, John and Pach, János and Pollack, Richard and Seidel, Raimund and Sharir, Micha and Snoeyink, Jack},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {523 -- 539},
  publisher    = {Springer},
  title        = {{On arrangements of Jordan arcs with three intersections per pair}},
  doi          = {10.1007/BF02187745},
  volume       = {4},
  year         = {1989},
}

@article{4093,
  abstract     = {This paper investigates the combinatorial and computational aspects of certain extremal geometric problems in two and three dimensions. Specifically, we examine the problem of intersecting a convex subdivision with a line in order to maximize the number of intersections. A similar problem is to maximize the number of intersected facets in a cross-section of a three-dimensional convex polytope. Related problems concern maximum chains in certain families of posets defined over the regions of a convex subdivision. In most cases we are able to prove sharp bounds on the asymptotic behavior of the corresponding extremal functions. We also describe polynomial algorithms for all the problems discussed.},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {139 -- 181},
  publisher    = {Springer},
  title        = {{The complexity of cutting complexes}},
  doi          = {10.1007/BF02187720},
  volume       = {4},
  year         = {1989},
}

@article{4100,
  abstract     = {This paper investigates the existence of linear space data structures for range searching. We examine thehomothetic range search problem, where a setS ofn points in the plane is to be preprocessed so that for any triangleT with sides parallel to three fixed directions the points ofS that lie inT can be computed efficiently. We also look atdomination searching in three dimensions. In this problem,S is a set ofn points inE 3 and the question is to retrieve all points ofS that are dominated by some query point. We describe linear space data structures for both problems. The query time is optimal in the first case and nearly optimal in the second.
},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {113 -- 126},
  publisher    = {Springer},
  title        = {{Linear space data structures for two types of range search}},
  doi          = {10.1007/BF02187875},
  volume       = {2},
  year         = {1987},
}

@article{4108,
  abstract     = {We propose a uniform and general framework for defining and dealing with Voronoi diagrams. In this framework a Voronoi diagram is a partition of a domainD induced by a finite number of real valued functions onD. Valuable insight can be gained when one considers how these real valued functions partitionD ×R. With this view it turns out that the standard Euclidean Voronoi diagram of point sets inR d along with its order-k generalizations are intimately related to certain arrangements of hyperplanes. This fact can be used to obtain new Voronoi diagram algorithms. We also discuss how the formalism of arrangements can be used to solve certain intersection and union problems.},
  author       = {Edelsbrunner, Herbert and Seidel, Raimund},
  issn         = {1432-0444},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {25 -- 44},
  publisher    = {Springer},
  title        = {{Voronoi diagrams and arrangements}},
  doi          = {10.1007/BF02187681},
  volume       = {1},
  year         = {1986},
}