@article{2419,
  abstract     = {For an absolutely continuous probability measure μ. on ℝd and a nonnegative integer k, let S̃k(μ, 0) denote the probability that the convex hull of k + d + 1 random points which are i.i.d. according to μ contains the origin 0. For d and k given, we determine a tight upper bound on S̃k(μ, 0), and we characterize the measures in ℝd which attain this bound. As we will see, this result can be considered a continuous analogue of the Upper Bound Theorem for the maximal number of faces of convex polytopes with a given number of vertices. For our proof we introduce so-called h-functions, continuous counterparts of h-vectors of simplicial convex polytopes.},
  author       = {Wagner, Uli and Welzl, Emo},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {2},
  pages        = {205 -- 219},
  publisher    = {Springer},
  title        = {{A continuous analogue of the Upper Bound Theorem}},
  doi          = {10.1007/s00454-001-0028-9},
  volume       = {26},
  year         = {2001},
}

@article{4007,
  abstract     = {This paper describes an algorithm for maintaining an approximating triangulation of a deforming surface in R 3 . The surface is the envelope of an infinite family of spheres defined and controlled by a finite collection of weighted points. The triangulation adapts dynamically to changing shape, curvature, and topology of the surface. },
  author       = {Cheng, Ho and Dey, Tamal and Edelsbrunner, Herbert and Sullivan, John},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {4},
  pages        = {525 -- 568},
  publisher    = {Springer},
  title        = {{Dynamic skin triangulation}},
  doi          = {10.1007/s00454-001-0007-1},
  volume       = {25},
  year         = {2001},
}

@article{4004,
  abstract     = {In this paper we introduce the abacus model of a simplex and use it to subdivide a d-simplex into k(d) d-simplices all of the same volume and shape characteristics. The construction is an extension of the subdivision method of Freudenthal [3] and has been used by Goodman and Peters [4] to design smooth manifolds.},
  author       = {Edelsbrunner, Herbert and Grayson, Daniel},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {4},
  pages        = {707 -- 719},
  publisher    = {Springer},
  title        = {{Edgewise subdivision of a simplex}},
  doi          = {10.1007/s004540010063},
  volume       = {24},
  year         = {2000},
}

@article{4014,
  abstract     = {A new paradigm for designing smooth surfaces is described. A finite set of points with weights specifies a closed surface in space referred to as skin. It consists of one or more components, each tangent continuous and free of self-intersections and intersections with other components. The skin varies continuously with the weights and locations of the points, and the variation includes the possibility of a topology change facilitated by the violation of tangent continuity at a single point in space and time. Applications of the skin to molecular modeling and to geometric deformation are discussed.},
  author       = {Edelsbrunner, Herbert},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {87 -- 115},
  publisher    = {Springer},
  title        = {{Deformable smooth surface design}},
  doi          = {10.1007/PL00009412},
  volume       = {21},
  year         = {1999},
}

@article{4022,
  abstract     = {A halving hyperplane of a set S of n points in R(d) contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two half-spaces. We prove bounds on the number of halving hyperplanes under the condition that the ratio of largest over smallest distance between any two points is at most delta n(1/d), delta some constant. Such a set S is called dense. In d = 2 dimensions the number of halving lines for a dense set can be as much as Omega(n log n), and it cannot exceed O (n(5/4)/log* n). The upper bound improves over the current best bound of O (n(3/2)/log* n) which holds more generally without any density assumption. In d = 3 dimensions we show that O (n(7/3)) is an upper bound on the number of halving planes for a dense set, The proof is based on a metric argument that can be extended to d greater than or equal to 4 dimensions, where it leads to O (n(d-2/d)) as an upper bound for the number of halving hyperplanes.},
  author       = {Edelsbrunner, Herbert and Valtr, Pavel and Welzl, Emo},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {3},
  pages        = {243 -- 255},
  publisher    = {Springer},
  title        = {{Cutting dense point sets in half}},
  doi          = {10.1007/PL00009291},
  volume       = {17},
  year         = {1997},
}

@article{4023,
  abstract     = {Let B be a finite pseudodisk collection in the plane. By the principle of inclusion-exclusion, the area or any other measure of the union is [GRAPHICS] We show the existence of a two-dimensional abstract simplicial complex, X subset of or equal to 2(B), so the above relation holds even if X is substituted for 2(B). In addition, X can be embedded in R(2) SO its underlying space is homotopy equivalent to int Boolean OR B, and the frontier of X is isomorphic to the nerve of the set of boundary contributions.},
  author       = {Edelsbrunner, Herbert and Ramos, Edgar},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {3},
  pages        = {287 -- 306},
  publisher    = {Springer},
  title        = {{Inclusion-exclusion complexes for pseudodisk collections}},
  doi          = {10.1007/PL00009295},
  volume       = {17},
  year         = {1997},
}

@article{4028,
  abstract     = {Efficient algorithms are described for computing topological, combinatorial, and metric properties of the union of finitely many spherical balls in R(d) These algorithms are based on a simplicial complex dual to a decomposition of the union of balls using Voronoi cells, and on short inclusion-exclusion formulas derived from this complex. The algorithms are most relevant in R(3) where unions of finitely many balls are commonly used as models of molecules.},
  author       = {Edelsbrunner, Herbert},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {415 -- 440},
  publisher    = {Springer},
  title        = {{The union of balls and its dual shape}},
  doi          = {10.1007/BF02574053},
  volume       = {13},
  year         = {1995},
}

@article{4035,
  abstract     = {Let S be a set of n points in ℝd . A set W is a weak ε-net for (convex ranges of)S if, for any T⊆S containing εn points, the convex hull of T intersects W. We show the existence of weak ε-nets of size {Mathematical expression}, where β2=0, β3=1, and βd ≈0.149·2d-1(d-1)!, improving a previous bound of Alon et al. Such a net can be computed effectively. We also consider two special cases: when S is a planar point set in convex position, we prove the existence of a net of size O((1/ε) log1.6(1/ε)). In the case where S consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of size O(1/ε), which improves a previous bound of Capoyleas.},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert and Grigni, Michelangelo and Guibas, Leonidas and Sharir, Micha and Welzl, Emo},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {1 -- 15},
  publisher    = {Springer},
  title        = {{Improved bounds on weak ε-nets for convex sets}},
  doi          = {10.1007/BF02574025},
  volume       = {13},
  year         = {1995},
}

@article{4032,
  abstract     = {Every collection of t≥2 n2 triangles with a total of n vertices in ℝ3 has Ω(t4/n6) crossing pairs. This implies that one of their edges meets Ω(t3/n6) of the triangles. From this it follows that n points in ℝ3 have only O(n8/3) halving planes.},
  author       = {Dey, Tamal and Edelsbrunner, Herbert},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {281 -- 289},
  publisher    = {Springer},
  title        = {{Counting triangle crossings and halving planes}},
  doi          = {10.1007/BF02574381},
  volume       = {12},
  year         = {1994},
}

@article{4040,
  abstract     = {A plane geometric graph C in ℝ2 conforms to another such graph G if each edge of G is the union of some edges of C. It is proved that, for every G with n vertices and m edges, there is a completion of a Delaunay triangulation of O(m2 n) points that conforms to G. The algorithm that constructs the points is also described.},
  author       = {Edelsbrunner, Herbert and Tan, Tiow},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {197 -- 213},
  publisher    = {Springer},
  title        = {{An upper bound for conforming Delaunay triangulations}},
  doi          = {10.1007/BF02573974},
  volume       = {10},
  year         = {1993},
}

@article{4044,
  abstract     = {Edge insertion iteratively improves a triangulation of a finite point set in ℜ2 by adding a new edge, deleting old edges crossing the new edge, and retriangulating the polygonal regions on either side of the new edge. This paper presents an abstract view of the edge insertion paradigm, and then shows that it gives polynomial-time algorithms for several types of optimal triangulations, including minimizing the maximum slope of a piecewise-linear interpolating surface.},
  author       = {Bern, Marshall and Edelsbrunner, Herbert and Eppstein, David and Mitchell, Stephen and Tan, Tiow},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {47 -- 65},
  publisher    = {Springer},
  title        = {{Edge insertion for optimal triangulations}},
  doi          = {10.1007/BF02573962},
  volume       = {10},
  year         = {1993},
}

@article{4045,
  abstract     = {We apply Megiddo's parametric searching technique to several geometric optimization problems and derive significantly improved solutions for them. We obtain, for any fixed ε>0, an O(n1+ε) algorithm for computing the diameter of a point set in 3-space, an O(8/5+ε) algorithm for computing the width of such a set, and on O(n8/5+ε) algorithm for computing the closest pair in a set of n lines in space. All these algorithms are deterministic.},
  author       = {Chazelle, Bernard and Edelsbrunner, Herbert and Guibas, Leonidas and Sharir, Micha},
  issn         = {0179-5376},
  journal      = {Discrete & Computational Geometry},
  number       = {1},
  pages        = {183 -- 196},
  publisher    = {Springer},
  title        = {{Diameter, width, closest line pair, and parametric searching}},
  doi          = {10.1007/BF02573973},
  volume       = {10},
  year         = {1993},
}

@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},
}