Search

A set P = H cup {w} of n+1 points in the plane is called a wheel set if all points but w are extreme. We show that for the purpose of counting crossing-free geometric graphs on P, it suffices to know the so-called frequency vector of P. While there are roughly 2^n distinct order types that correspond to wheel sets, the number of frequency vectors is only about 2^{n/2}. We give simple formulas in terms of the frequency vector for the number of crossing-free spanning cycles, matchings, w-embracing triangles, and many more. Based on these formulas, the corresponding numbers of graphs can be computed efficiently. Also in higher dimensions, wheel sets turn out to be a suitable model to approach the problem of computing the simplicial depth of a point w in a set H, i.e., the number of simplices spanned by H that contain w. While the concept of frequency vectors does not generalize easily, we show how to apply similar methods in higher dimensions. The result is an O(n^{d-1}) time algorithm for computing the simplicial depth of a point w in a set H of n d-dimensional points, improving on the previously best bound of O(n^d log n). Configurations equivalent to wheel sets have already been used by Perles for counting the faces of high-dimensional polytopes with few vertices via the Gale dual. Based on that we can compute the number of facets of the convex hull of n=d+k points in general position in R^d in time O(n^max(omega,k-2)) where omega = 2.373, even though the asymptotic number of facets may be as large as n^k., Leibniz International Proceedings in Informatics (LIPIcs), 77, ISSN:1868-8969, 33rd International Symposium on Computational Geometry (SoCG 2017), ISBN:978-3-95977-038-5

Let S be a set of n points in d-space, no i + 1 points on a common (i?l)-flat for 1 ≤ i ≤ d. An oriented (d ? 1)-simplex spanned by d points in S is called a j-facet of S if there are exactly j points from S on the positive side of its affine hull. We show: (*) For j ≤ n/2 ? 2, the total number of (≤ j)- facets (i.e. the number of i- facets with 0 ≤ i ≤ j) in 3 -space is maximized in convex position (where these numbers are known). A large part of this presentation is a preparatory review of some basic properties of the collection of j-facets--some with their proofs--and of relations to well-established concepts and results from the theory of convex polytopes (h-vector, Dehn-Sommerville relations, Upper Bound Theorem, Generalized Lower Bound Theorem). The relations are established via a duality closely related to the Gale transform--similar to previous works by Lee, by Clarkson, and by Mulmuley. A central definition is as follows. Given a directed line l and a j-facet F of S, we say that l enters F if l intersects the relative interior of F in a single point, and if l is directed from the positive to the negative side of F. One of the results reviewed is a tight upper bound of % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfeBSjuyZL2yd9gzLbvyNv2CaerbuLwBLn% hiov2DGi1BTfMBaeXatLxBI9gBaerbd9wDYLwzYbItLDharqqtubsr% 4rNCHbGeaGqiVu0Je9sqqrpepC0xbbL8F4rqqrFfpeea0xe9Lq-Jc9% vqaqpepm0xbba9pwe9Q8fs0-yqaqpepae9pg0FirpepeKkFr0xfr-x% fr-xb9adbaqaaeGaciGaaiaabeqaamaabaabaaGcbaWaaeWaaqaabe% qaaiaadQgacqGHRaWkcaWGKbGaeyOeI0IaaGymaaqaaiacaci5aaaa% dsgacWaGasoaaaGHsislcGaGasoaaaaIXaaaaiaawIcacaGLPaaaaa% a!4434! $$\left( \begin{gathered} j + d - 1 \hfill \\ d - 1 \hfill \\ \end{gathered} \right)$$ on the maximum number of j-facets entered by a directed line. Based on these considerations, we also introduce a vector for a point relative to a point set, which--intuitively speaking--expresses "how interior" the point is relative to the point set. This concept allows us to show that statement (*) above is equivalent to the Generalized Lower Bound Theorem for d-polytopes with at most d + 4 vertices.

Random sampling is an efficient method to deal with constrained optimization problems in computational geometry. In a first step, one finds the optimal solution subject to a random subset of the constraints; in many cases, the expected number of constraints still violated by that solution is then significantly smaller than the overall number of constraints that remain. This phenomenon can be exploited in several ways, and typically results in simple and asymptotically fast algorithms. Very often the analysis of random sampling in this context boils down to a simple identity (the sampling lemma ) which holds in a general framework, yet has not been stated explicitly in the literature. In the more restricted but still general setting of LP-type problems , we prove tail estimates for the sampling lemma, giving Chernoff-type bounds for the number of constraints violated by the solution of a random subset. As an application, we provide the first theoretical analysis of multiple pricing , a heuristic used in the simplex method for linear programming in order to reduce a large problem to few small ones. This follows from our analysis of a reduction scheme for general LP-type problems, which can be considered as a simplification of an algorithm due to Clarkson. The simplified version needs less random resources and allows a Chernoff-type tail estimate.

We present an algorithm for computing the discrete 2-center of a set P of n points in the plane; that is, computing two congruent disks of smallest possible radius, centered at two points of P , whose union covers P . Our algorithm runs in time O(n 4/3 log 5 n) .

LetS be a set ofn points in ?d. A setW is aweak ?-net for (convex ranges of)S if, for anyT⊆S containing ?n points, the convex hull ofT intersectsW. We show the existence of weak ?-nets of size % MathType!MTEF!2!1!+-% feaafiart1ev1aaatCvAUfKttLearuqr1ngBPrgarmWu51MyVXgatC% vAUfeBSjuyZL2yd9gzLbvyNv2CaeHbd9wDYLwzYbItLDharyavP1wz% ZbItLDhis9wBH5garqqtubsr4rNCHbGeaGqiVu0Je9sqqrpepC0xbb% L8F4rqqrFfpeea0xe9Lq-Jc9vqaqpepm0xbba9pwe9Q8fs0-yqaqpe% pae9pg0FirpepeKkFr0xfr-xfr-xb9adbaqaaeGaciGaaiaabeqaam% aaeaqbaaGcbaGaem4ta8KaeiikaGIaeiikaGIaeGymaeJaei4la8Ia% eqyTdu2aaWbaaSqabeaacqWGKbazaaGccqGGPaqkcyGGSbaBcqGGVb% WBcqGGNbWzdaahaaWcbeqaaiabek7aInaaBaaameaacqWGKbazaeqa% aaaakiabcIcaOiabigdaXiabc+caViabew7aLjabcMcaPiabcMcaPa% aa!50FE! $$O((1/\varepsilon ^d )\log ^{\beta _d } (1/\varepsilon ))$$ , whereβ2=0,β3=1, andβd?0.149·2d-1(d-1)!, improving a previous bound of Alonet al. Such a net can be computed effectively. We also consider two special cases: whenS is a planar point set in convex position, we prove the existence of a net of sizeO((1/?) log1.6(1/?)). In the case whereS consists of the vertices of a regular polygon, we use an argument from hyperbolic geometry to exhibit an optimal net of sizeO(1/?), which improves a previous bound of Capoyleas.

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 ?(m2/3n2/3 +n), and that it isO(m2/3n2/3s(n) +n) forn unit-circles, wheres(n) (and laters(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(m3/5n4/5s(n) +n). The same bounds (without thes(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(m4/7n9/7s(m, n) +n2), in general, andO(m3/4n3/4s(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(m3/2s(m)) which improves the best previous upper bound on this problem. Applications of our results to other distance problems are also given.

We consider the problem of computing geometric transformations (rotation, translation, reflexion) that map a point set A exactly or approximately into a point set B. We derive efficient algorithms for various cases (Euclidian or maximum metric, translation or rotation or general congruence).

We demonstrate the existence of data structures for half-space and simplex range queries on finite point sets ind-dimensional space,dÂ?2, with linear storage andO(nÂ?) query time, $$\alpha = \frac{{d(d - 1)}}{{d(d - 1) + 1}} + \gamma for all \gamma > 0$$ . These bounds are better than those previously published for alldÂ?2. Based on ideas due to Vapnik and Chervonenkis, we introduce the concept of an Â?-net of a set of points for an abstract set of ranges and give sufficient conditions that a random sample is an Â?-net with any desired probability. Using these results, we demonstrate how random samples can be used to build a partition-tree structure that achieves the above query time.

For a setS ofn points in the plane and forK ⊆ {1, 2, ..., [1/2n]}, letfK(S) denote the number of subsets ofS with cardinalityk ?K which can be cut offS by a straight line. We show that there is a positive constantc such thatfK(S)

The range-searching problems that allow efficient partition trees are characterized as those defined by range spaces of finite Vapnik-Chervonenkis dimension. More generally, these problems are shown to be the only ones that admit linear-size solutions with sublinear query time in the arithmetic model. The proof rests on a characterization of spanning trees with a low stabbing number. We use probabilistic arguments to treat the general case, but we are able to use geometric techniques to handle the most common range-searching problems, such as simplex and spherical range search. We prove that any set ofn points inEd admits a spanning tree which cannot be cut by any hyperplane (or hypersphere) through more than roughlyn1Â?1/d edges. This result yields quasi-optimal solutions to simplex range searching in the arithmetic model of computation. We also look at polygon, disk, and tetrahedron range searching on a random access machine. Givenn points inE2, we derive a data structure of sizeO(n logn) for counting how many points fall inside a query convexk-gon (for arbitrary values ofk). The query time isO(Â?kn logn). Ifk is fixed once and for all (as in triangular range searching), then the storage requirement drops toO(n). We also describe anO(n logn)-size data structure for counting how many points fall inside a query circle inO(Â?n log2n) query time. Finally, we present anO(n logn)-size data structure for counting how many points fall inside a query tetrahedron in 3-space inO(n2/3 log2n) query time. All the algorithms are optimal within polylogarithmic factors. In all cases, the preprocessing can be done in polynomial time. Furthermore, the algorithms can also handle reporting within the same complexity (adding the size of the output as a linear term to the query time).