Abstract Let $$n \in \mathbb {N}$$ n ∈ N and $$k \in \mathbb {N}_0$$ k ∈ N 0 . Given a set P of n points in the plane, a pair $$\{p,q\}$$ { p , q } of points in P is called k-deep, if there are at least k points from P strictly on each side of the line spanned by p and q. A k-deep clique is a subset of P with all its pairs k-deep. We show that if P is in general position (i.e., no three points on a line), there is a k-deep clique of size at least $$ \max \{1,\lfloor \frac{n}{k+1} \rfloor \}$$ max { 1 , ⌊ n k + 1 ⌋ } ; this is tight, for example in convex position. A k-deep clique in any set P of n points cannot have size exceeding $$n-\lceil \frac{3k}{2} \rceil $$ n - ⌈ 3 k 2 ⌉ ; this is tight for $$k \le \frac{n}{3}$$ k ≤ n 3 . Moreover, for $$k \le \lfloor \frac{n}{2} \rfloor - 1$$ k ≤ ⌊ n 2 ⌋ - 1 , a k-deep clique cannot have size exceeding $$2\sqrt{n(\lfloor \frac{n}{2} \rfloor -k)}$$ 2 n ( ⌊ n 2 ⌋ - k ) ; this is tight within a constant factor. We also pay special attention to $$(\frac{n}{2}-1)$$ ( n 2 - 1 ) -deep cliques (for n even), which are called halving cliques. These have been considered in the literature by Khovanova and Yang, 2012, and they play a role in the latter bound above. Every set P in general position with a halving clique Q of size m must have at least $$\lfloor \frac{(m-1)(m+3)}{2}\rfloor $$ ⌊ ( m - 1 ) ( m + 3 ) 2 ⌋ points. If Q is in convex position, the set P must have size at least $$m(m-1)$$ m ( m - 1 ) . This is tight, i.e., there are sets $$Q_m$$ Q m of m points in convex position which can be extended to a set of $$m(m-1)$$ m ( m - 1 )

We establish the following two main results on order types of points in general position in the plane (realizable simple planar order types, realizable uniform acyclic oriented matroids of rank 3): (a) The number of extreme points in an n -point order type, chosen uniformly at random from all such order types, is on average 4+ o (1). For labeled order types, this number has average \(4- \mbox{$\frac{8}{n^2 - n +2}$}\) and variance at most 3. (b) The (labeled) order types read off a set of n points sampled independently from the uniform measure on a convex planar domain, smooth or polygonal, or from a Gaussian distribution are concentrated, i.e., such sampling typically encounters only a vanishingly small fraction of all order types of the given size. Result (a) generalizes to arbitrary dimension d for labeled order types with the average number of extreme points 2 d + o (1) and constant variance. We also discuss to what extent our methods generalize to the abstract setting of uniform acyclic oriented matroids. Moreover, our methods show the following relative of the Erdős-Szekeres theorem: for any fixed k , as n → ∞, a proportion 1 - O (1/ n ) of the n -point simple order types contain a triangle enclosing a convex k -chain over an edge. For the unlabeled case in (a), we prove that for any antipodal, finite subset of the two-dimensional sphere, the group of orientation preserving bijections is cyclic, dihedral, or one of A 4 , S 4 , or A 5 (and each case is possible). These are the finite subgroups of SO (3) and our proof follows the lines of their characterization by Felix Klein.

Abstract Given a finite point setPingeneral positionin the plane, afull triangulationofPis a maximal straight-line embedded plane graph on P. Apartial triangulationofPis a full triangulation of some subset $$P'$$ P′ ofPcontaining all extreme points in P. Abistellar flipon a partial triangulation either flips an edge (callededge flip), removes a non-extreme point of degree 3, or adds a point in $$P \setminus P'$$ P\P′ as vertex of degree 3. Thebistellar flip graphhas all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. Theedge flip graphis defined with full triangulations as vertices, and edge flips determining the adjacencies. Lawson showed in the early seventies that these graphs are connected. The goal of this paper is to investigate the structure of these graphs, with emphasis on their vertex connectivity. For setsPofnpoints in the plane in general position, we show that the edge flip graph is $$\lceil {n}/{2}-2\rceil $$ ⌈n/2-2⌉ -vertex connected, and the bistellar flip graph is $$(n-3)$$ (n-3) -vertex connected; both results are tight. The latter bound matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points to 3-space and projecting back the lower convex hull), where $$(n-3)$$ (n-3) -vertex connectivity has been known since the late eighties through the secondary polytope due to Gelfand, Kapranov, & Zelevinsky and Balinski’s Theorem. For the edge flip-graph, we additionally show that the vertex connectivity is at least as large as (and hence equal to) the minimum degree (i.e., the minimum number of flippable edges in any full triangulation), provided thatnis large enough. Our methods also yield several other results: (i) The edge flip graph can be covered by graphs of polytopes of dimension $$\lceil {n}/{2} -2\rceil $$ ⌈n/2-2⌉ (products of associahedra) and the bistellar flip graph can be covered by graphs of polytopes of dimension $$n-3$$ n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance $$n-3$$ n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations of a point set are regular iff the partial order of partial subdivisions has height $$n-3$$ n-3 . (iv) There are arbitrarily large setsPwith non-regular partial triangulations and such that every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular triangulations.

Suppose we are sending out k robots from 0 to search the real line at constant speed (with turns) to find a target at an unknown location; f of the robots are faulty, meaning that they fail to report the target although visiting its location (called crash type). The goal is to find the target in time at most $$\lambda |x|$$ , if the target is located at x, $$|x| \ge 1$$ , for $$\lambda $$ as small as possible. We show that this cannot be achieved for $$\begin{aligned}&\lambda < 2\frac{\rho ^\rho }{(\rho -1)^{\rho -1}}+1,~~ \rho := \frac{2(f+1)}{k}~, \end{aligned}$$ which is tight due to earlier work (see Czyzowitz et al. in Proc PODC’16, pp 405–414, 2016, where this problem was introduced). This also gives some better than previously known lower bounds for so-called Byzantine-type faulty robots that may actually wrongly report a target. In the second part of the paper we deal with the m-rays generalization of the problem, where the hidden target is to be detected on m rays all emanating at the same point. Using a generalization of our methods, along with a useful relaxation of the original problem, we establish a tight lower for this setting as well (as above, with $$\rho := \nicefrac {m(f+1)}{k}$$ ). When specialized to the case $$f=0$$ , this resolves the question on parallel search on m rays, posed by three groups of scientists some 15–30 years ago: by Baeza-Yates, Culberson, and Rawlins; by Kao, Ma, Sipser, and Yin; and by Bernstein, Finkelstein, and Zilberstein. The m-rays generalization is known to have connections to other, seemingly unrelated, problems, including hybrid algorithms for on-line problems, and so-called contract algorithms.

Given a finite point set P in general position in the plane, a full triangulation is a maximal straight-line embedded plane graph on P. A partial triangulation on P is a full triangulation of some subset P' of P containing all extreme points in P. A bistellar flip on a partial triangulation either flips an edge, removes a non-extreme point of degree 3, or adds a point in P ⧵ P' as vertex of degree 3. The bistellar flip graph has all partial triangulations as vertices, and a pair of partial triangulations is adjacent if they can be obtained from one another by a bistellar flip. The goal of this paper is to investigate the structure of this graph, with emphasis on its connectivity. For sets P of n points in general position, we show that the bistellar flip graph is (n-3)-connected, thereby answering, for sets in general position, an open questions raised in a book (by De Loera, Rambau, and Santos) and a survey (by Lee and Santos) on triangulations. This matches the situation for the subfamily of regular triangulations (i.e., partial triangulations obtained by lifting the points and projecting the lower convex hull), where (n-3)-connectivity has been known since the late 1980s through the secondary polytope (Gelfand, Kapranov, Zelevinsky) and Balinski’s Theorem. Our methods also yield the following results (see the full version [Wagner and Welzl, 2020]): (i) The bistellar flip graph can be covered by graphs of polytopes of dimension n-3 (products of secondary polytopes). (ii) A partial triangulation is regular, if it has distance n-3 in the Hasse diagram of the partial order of partial subdivisions from the trivial subdivision. (iii) All partial triangulations are regular iff the trivial subdivision has height n-3 in the partial order of partial subdivisions. (iv) There are arbitrarily large sets P with non-regular partial triangulations, while every proper subset has only regular triangulations, i.e., there are no small certificates for the existence of non-regular partial triangulations (answering a question by F. Santos in the unexpected direction).

This dataset contains the reproducible research package for the preprint "Exact Value of M(8) and Sharp Bounds for Great-Circle Cell Expectations", addressing Oberwolfach Report 3/2024 "Open Problems in Discrete Geometry", Problem 8 (posed by Xavier Goaoc). Problem. Let S be a simple arrangement of n great circles on the sphere S^2 and choose a 2-dimensional cell c uniformly at random. Let S' be the circles that do not touch c, and let c' be the cell of the subarrangement S' that contains c. Define M(n) as the maximum, over all simple arrangements, of the expected number of edges of c'. Main results: - Theorem 1: exact value M(8) = 113/29, obtained by exhaustive enumeration over all 3,315 simple 8-point order types in the Aichholzer database; the extremal order-type index is 1026. - Theorem 2: for the regular near-pencil family, the closed-form expectation E[x] = (8 n^2 - 36 n) / (n^2 - n + 2) = 8 - O(1/n), giving M(n) >= 8 - O(1/n) for all n >= 6. - Theorem 3: general upper bound M(n) <= n(n-2)(n-3)/(n^2 - n + 2) = n - 4 + O(1/n^2) for all n >= 3. - Conjecture: the matching upper bound M(n) <= 8 + o(1) remains open; M(n) = 8 - o(1) is therefore a conjecture supported by numerical experiments. The archive includes Python scripts (MIT License), JSON data certificates and the Aichholzer order-type database (CC0 1.0 Universal), proof notes, review reports, and the preprint in PDF and Markdown form (CC-BY 4.0). Limitations: exact values are known only for n <= 8; the asymptotic upper bound is not proved.

Consider the following simple coloring algorithm for a graph on n vertices. Each vertex chooses a color from {1, ..., Δ(G) + 1} uniformly at random. While there exists a conflicted vertex choose one such vertex uniformly at random and recolor it with a randomly chosen color. This algorithm was introduced by Bhartia et al. [MOBIHOC'16] for channel selection in WIFI-networks. We show that this algorithm always converges to a proper coloring in expected O(n log Δ) steps, which is optimal and proves a conjecture of Chakrabarty and de Supinski [SOSA'20].

In a straight-line embedded triangulation of a point set P in the plane, removing an inner edge and—provided the resulting quadrilateral is convex—adding the other diagonal is called an edge flip. The (edge) flip graph has all triangulations as vertices, and a pair of triangulations is adjacent if they can be obtained from each other by an edge flip. The goal of this paper is to contribute to a better understanding of the flip graph, with an emphasis on its connectivity. For sets in general position, it is known that every triangulation allows at least edge flips (a tight bound) which gives the minimum degree of any flip graph for n points. We show that for every point set P in general position, the flip graph is at least -vertex connected. Somewhat more strongly, we show that the vertex connectivity equals the minimum degree occurring in the flip graph, i.e. the minimum number of flippable edges in any triangulation of P, provided P is large enough. Finally, we exhibit some of the geometry of the flip graph by showing that the flip graph can be covered by 1-skeletons of polytopes of dimension (products of associahedra). A corresponding result ((n – 3)-vertex connectedness) can be shown for the bistellar flip graph of partial triangulations, i.e. the set of all triangulations of subsets of P which contain all extreme points of P. This will be treated separately in a second part.

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.

We investigate parameterizing hard combinatorial problems by the size of the solution set compared to all solution candidates. Our main result is a uniform sampling algorithm for satisfying assignments of 2-CNF formulas that runs in expected time O^*(eps^{-0.617}) where eps is the fraction of assignments that are satisfying. This improves significantly over the trivial sampling bound of expected Theta^*(eps^{-1}), and on all previous algorithms whenever eps = Omega(0.708^n). We also consider algorithms for 3-SAT with an eps fraction of satisfying assignments, and prove that it can be solved in O^*(eps^{-2.27}) deterministic time, and in O^*(eps^{-0.936}) randomized time. Finally, to further demonstrate the applicability of this framework, we also explore how similar techniques can be used for vertex cover problems.

Given P and P', equally sized planar point sets in general position, we call a bijection from P to P' crossing-preserving if crossings of connecting segments in P are preserved in P' (extra crossings may occur in P'). If such a mapping exists, we say that P' crossing-dominates P, and if such a mapping exists in both directions, P and P' are called crossing-equivalent. The relation is transitive, and we have a partial order on the obtained equivalence classes (called crossing types or x-types). Point sets of equal order type are clearly crossing-equivalent, but not vice versa. Thus, x-types are a coarser classification than order types. (We will see, though, that a collapse of different order types to one x-type occurs for sets with triangular convex hull only.) We argue that either the maximal or the minimal x-types are sufficient for answering many combinatorial (existential or extremal) questions on planar point sets. Motivated by this we consider basic properties of the relation. We characterize order types crossing-dominated by points in convex position. Further, we give a full characterization of minimal and maximal abstract order types. Based on that, we provide a polynomial-time algorithm to check whether a point set crossing-dominates another. Moreover, we generate all maximal and minimal x-types for small numbers of points.

We derive improved upper bounds on the number of crossing-free straight-edge spanning cycles (also known as Hamiltonian tours and simple polygonizations) that can be embedded over any specific set of N points in the plane. More specifically, we bound the ratio between the number of spanning cycles (or perfect matchings) that can be embedded over a point set and the number of triangulations that can be embedded over it. The respective bounds are O(1.8181N) for cycles and O(1.1067N) for matchings. These imply a new upper bound of O(54.543N) on the number of crossing-free straight-edge spanning cycles that can be embedded over any specific set of N points in the plane (improving upon the previous best upper bound O(68.664N)). Our analysis is based on a weighted variant of Kasteleyn's linear algebra technique.

We study the expected number of interior vertices of degree i in a triangulation of a point set S, drawn uniformly at random from the set of all triangulations of S, and derive various bounds and inequalities for these expected values. One of our main results is: For any set S of N points in general position, and for any fixed i, the expected number of vertices of degree i in a random triangulation is at least γiN, for some fixed positive constant γi (assuming that N > i and that at least some fixed fraction of the points are interior).

In this work we study the problem of determining the throughput capacity of a wireless network. We propose a scheduling algorithm to achieve this capacity within an approximation factor. Our analysis is performed in the physical interference model, where nodes are arbitrarily distributed in Euclidean space. We consider the problem separately from the routing problem and the power control problem, i.e., all requests are single-hop, and all nodes transmit at a fixed power level. The existing solutions to this problem have either concentrated on special-case topologies, or presented optimality guarantees which become arbitrarily bad (linear in the number of nodes) depending on the network's topology. We propose the first scheduling algorithm with approximation guarantee independent of the topology of the network. The algorithm has a constant approximation guarantee for the problem of maximizing the number of links scheduled in one time-slot. Furthermore, we obtain a O(log n) approximation for the problem of minimizing the number of time slots needed to schedule a given set of requests. Simulation results indicate that our algorithm does not only have an exponentially better approximation ratio in theory, but also achieves superior performance in various practical network scenarios. Furthermore, we prove that the analysis of the algorithm is extendable to higher-dimensional Euclidean spaces, and to more realistic bounded-distortion spaces, induced by non-isotropic signal distortions. Finally, we show that it is NP-hard to approximate the scheduling problem to within n1-epsivfactor, for any constant epsiv > 0, in the non-geometric SINR model, in which path-loss is independent of the Euclidean coordinates of the nodes.

We propose a scalably efficient scheme for detecting large-scale physically correlated events in sensor networks. Specifically, we show that in a network of n sensors arbitrarily distributed in the plane, a sample of O (1/ϵ log 1/ϵ) sensor nodes ( mice ) is sufficient to catch any, and only those , events that affect Ω (ϵ n ) nodes ( elephants ), for any 0 < ϵ < 1, as long as the geometry of the event has a bounded Vapnik-Chervonenkis (VC) dimension. In fact, the scheme is provably able to estimate the size of an event within the approximation error of ±ϵ n /4, which can be improved further at the expense of more mice. The detection algorithm itself requires knowledge of the event geometry (e.g., circle, ellipse, or rectangle) for the sake of computational efficiency, but the combinatorial bound on the sample size (set of mice) depends only on the VC, dimension of the event class and not the precise shape geometry. While nearly optimal in theory, due to implicit constant factors, these “scale-free” bounds still prove too large in practice if applied blindly. We therefore propose heuristic improvements and perform empirical parameter tuning to counter the pessimism inherent in these theoretical estimates. Using a variety of data distributions and event geometries, we show through simulations that the final scheme is eminently scalable and practical, say, for n ≥ 1000. The overall simplicity and generality of our technique suggests that it is well suited for a wide class of sensornet applications, including monitoring of physical environments, network anomalies, network security, or any abstract binary event that affects a significant number of nodes in the network.

Given a set S of n points in R 3 , a point x in R 3 is called center point of S if every closed halfspace whose bounding hyperplane passes through x contains at least ⌈ n /4⌉ points from S . We present a near-quadratic algorithm for computing the center region , that is the set of all center points, of a set of n points in R 3 . This is nearly tight in the worst case since the center region can have Ω( n 2 ) complexity. We then consider sets S of 3 n points in the plane which are the union of three disjoint sets consisting respectively of n red, n blue, and n green points. A point x in R 2 is called a colored Tverberg point of S if there is a partition of S into n triples with one point of each color, so that x lies in all triangles spanned by these triples. We present a first polynomial-time algorithm for recognizing whether a given point is a colored Tverberg point of such a 3-colored set S .

We propose a scalably efficient scheme for detecting large-scale physically-correlated events in sensor networks. Specifically, we show that in a network of n sensors arbitrarily distributed in the plane, a sample of O(1/ε log 1/ε) sensor nodes (mice) is sufficient to catch any, and only those, events that affect Ω(εn) nodes (elephants), for any 0 < ε < 1, as long as the geometry of the event has a bounded Vapnik-Chervonenkis (VC) dimension. In fact, the scheme is provably able to estimate the size of an event within the approximation error of ±εn/4, which can be improved further at the expense of more mice. The detection algorithm itself requires knowledge of the event geometry (e.g. circle, ellipse, or rectangle) for the sake of computational efficiency, but the combinatorial bound on the sample size (set of mice) depends only on the VC dimension of the event class and not the precise shape geometry.

We consider an online version of the conflict‐free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict‐free, in the sense that in every interval I there is a color that appears exactly once in I. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring $\Omega(\sqrt{n})$ colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses $O(\log^2 n)$ colors, and the second is randomized and uses $O(\log n)$ colors with high probability. We also show that the $O(\log^2 n)$ bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only $O(\log n)$ colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case.

Let S be a finite set of n + 3 points in general position in the plane, with 3 extreme points and n interior points. We consider triangulations drawn uniformly at random from all triangulations of S, and investigate the expected number, ˆvi, of interior points of degree i in such a triangulation. We provide bounds that are linear in n on these numbers. In particular, n/43 ≤ ˆv3 ≤ (2n + 3)/5. Moreover, we relate these results to the question about the maximum and minimum possible number of triangulations in such a set S, and show that the number of triangulations of any set of n points in the plane is at most 43 n, thereby improving on a previous bound by Santos and Seidel.

We show that a set of n points in the plane has at most $O(10.05^n)$ perfect matchings with crossing‐free straight‐line embedding. The expected number of perfect crossing‐free matchings of a set of n points drawn independently and identically distributed from an arbitrary distribution in the plane is at most $O(9.24^n)$. Several related bounds are derived: (a) The number of all (not necessarily perfect) crossing‐free matchings is at most $O(10.43^n)$. (b) The number of red‐blue perfect crossing‐free matchings (where the points are colored red or blue and each edge of the matching must connect a red point with a blue point) is at most $O(7.61^n)$. (c) The number of left‐right perfect crossing‐free matchings (where the points are designated as left or right endpoints of the matching edges) is at most $O(5.38^n)$. (d) The number of perfect crossing‐free matchings across a line (where all the matching edges must cross a fixed halving line of the set) is at most $4^n$. These bounds are employed to infer that a set of n points in the plane has at most $O(86.81^n)$ crossing‐free spanning cycles (simple polygonizations) and at most $O(12.24^n)$ crossing‐free partitions (these are partitions of the point set so that the convex hulls of the individual parts are pairwise disjoint). We also derive lower bounds for some of these quantities.

We present a near-quadratic algorithm for computing the center regionof a set of n points in three dimensions. This is nearly tight inthe worst case since the center region can have Ω(n2) complexity. We then consider the problem of recognizing whether a given point q is a colored Tverberg point of a set of n colored points in the plane, and present the first polynomial-time algorithm for this problem.

(MATH) Given a set L of n lines in $\reals^3$, let JL denote the set of all joints of L; joints are points in $\reals^3$ that are incident to at least three non-coplanar lines in L. We show that there are at most O(n 5/3) incidences between JL and L.(MATH) This result leads to related questions about incidences between L and a set P of m points in $\reals^3$: First, we associate with every point p ε P the minimum number of planes it takes to cover all lines incident to p. Then the sum of these numbers is at most $$ O(m^4/7n^5/7+m+n) ~. $$ Second, if each line forms a fixed given non-zero angle with the xy-plane---we say the lines are equally inclined--- then the number of (real) incidences is at most $$ O(\min\m^3/4n^1/2\kappa(m),m^4/7n^5/7\ + m + n) ~, $$ where $\kappa(m) = (\log m)^O(\alpha^2(m))$, and $\alpha(m)$ is the slowly growing inverse Ackermann function. These bounds are smaller than the tight Szemerédi-Trotter bound for point-line incidences in $\reals^2$, unless both bounds are linear. They are the first results of that type on incidences between points and 1-dimensional objects in $\reals^3$. This research was stimulated by a question raised by G. Elekes.

A recent result by Pach and Pinchasi on so-called balanced lines of a finite two-colored point set in the plane is related to other facts on halving triangles in 3-space and to a special case of the Generalized Lower Bound Theorem for convex polytopes.

Suppose we are given (the edge graph of) an n-dimensional hypercube with its edges oriented so that every face has a unique sink. Such an orientation is called a unique sink orientation, and we are interested in finding the unique sink of the whole cube, when the orientation is given implicitly. The basic operation available is the so-called vertex evaluation, where we can access an arbitrary vertex of the cube, for which we obtain the orientations of the incident edges. Unique sink orientations occur when the edges of a deformed geometric n-dimensional cube (i.e., a polytope with the combinatorial structure of a cube) are oriented according to some generic linear function. These orientations are easily seen to be acyclic. The main motivation for studying unique sink orientations are certain linear complementarity problems, which allow this combinatorial abstraction (due to Stickney and Watson, 1978), where orientations with cycles can arise. Similarly, some quadratic optimization problems, like computing the smallest enclosing ball of a finite point set, can be formulated as finding a sink in a unique sink orientation (with cycles possible). For acyclic unique sink orientations, randomized procedures due to Bernd Gartner (1998, 2001) with an expected number of at Most e/sup 2/spl radic/n/ vertex evaluations have been known. For the general case, a simple randomized (3/2)/sup n/ procedure exists (without explicit mention in the literature). We present new algorithms, a deterministic O(1.61/sup n/) procedure and a randomized O((43/20)/sup n/2/)=O(1.47/sup n/) procedure for unique sink orientations. An interesting aspect of these algorithms is that they do not proceed on a path to the sink (in a simplex-like fashion), but they exploit the potential of random access (in the sense of arbitrary access) to any vertex of the cube. We consider this feature the main contribution of the paper. We believe that unique sink orientations have a rich structure, and there is ample space for improvement on the bounds given above.

We analyze a randomized pivoting process involving one line and n points in the plane. The process models the behavior of the Random-Edge simplex algorithm on simple polytopes with n facets in dimension n-2. We obtain a tight O(\log^2 n) bound for the expected number of pivot steps. This is the first nontrivial bound for Random-Edge which goes beyond bounds for specific polytopes. The process itself can be interpreted as a simple algorithm for certain 2-variable linear programming problems, and we prove a tight t(n) bound for its expected runtime.The combinatorial structure behind the process is a directed graph over pairs of points, with arc orientations induced by the pivot steps. We characterize the class of graphs arising from one line and n points, up to oriented matroid realizability.

Article Free Access Share on Random sampling in geometric optimization: new insights and applications Authors: Bernd Gärtner Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, Switzerland Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, SwitzerlandView Profile , Emo Welzl Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, Switzerland Institut für Theoretische Informatik, ETH Zürich, ETH Zentrum, CH-8092 Zürich, SwitzerlandView Profile Authors Info & Claims SCG '00: Proceedings of the sixteenth annual symposium on Computational geometryMay 2000 Pages 91–99https://doi.org/10.1145/336154.336186Online:01 May 2000Publication History 8citation396DownloadsMetricsTotal Citations8Total Downloads396Last 12 Months11Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

For an absolutely continuous probability measure p on Ra and a normegative integer k, let Sh(#, 0) denote the probability that the convex hull of k + d + 1 random points which are i.i.d, according to p contains the origin 0. For d and k given, we determine a tight upper bound on Sk(p, 0), and we characterize the measures in ]R d which attain this bound.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 for simplicial convex polytopes.

Let P be a set of n. points in IRd in general position, i.e., no i + 1 points on a common (i -1)-flat, 1 < i 5 d.A k-set @'P is a set S of E points in P that can be separated from P \ S by a hyperplane.A j-facet of P is an oriented (d -l)simplex spanned by d points in P which has exactly j points from P on the positive side of its affine hull.If P is a planar point set and n is even, a halving edge is an undirected edge between two points, such that the connecting line has the same number of points on either side.The number of (n/2)-sets is twice the number of halving edges.Inspired by Dey's recent proof of a new bound on the number of k-sets we show that where degp is the number of halving edges incident to point p and C is the number of crossing pairs of halving edges.The identity allows us, among other things, to determine the masimum number of halving edges in a set of 12 points.An anaIogous identity holds for j-facets.For P in IR3 we show that for j 5 n/4 -2 the number of cs j)-facets (i.e., i-facets with 0 5 i 5 j) is maximized for sets in convex position, where this number is known to be (j + l)(j + 2)n -2(j + l)(j + 2)(j + 3)/3.For 1; 5 n/4 -1, k2n -k(k -1)(2A + 5)/3 is the tight upper bound for the number of (5 A)-sets (i.e., i-sets with 1 ': i 5 k).'h't of this work %S Performed while R.S. and E.W. were visiting the DlhfAa center in November 1989.while R.S. visited FU Berlin in 1992, while E.W. visited

Article Free Access Share on The discrete 2-center problem Authors: Pankaj K. Agarwal Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NC Center for Geometric Computing, Department of Computer Science, Box 90129, Duke University, Durham, NCView Profile , Micha Sharir School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NY School of Mathematical Sciences, Tel Aviv University, Tel Aviv 69978, Israel and Courant Institute of Mathematical Sciences, New York University, New York, NYView Profile , Emo Welzl Institut für Theoretische Informatik, ETH Zürich, CH-8092, Zürich, Switzerland Institut für Theoretische Informatik, ETH Zürich, CH-8092, Zürich, SwitzerlandView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 147–155https://doi.org/10.1145/262839.262921Published:01 August 1997Publication History 17citation328DownloadsMetricsTotal Citations17Total Downloads328Last 12 Months29Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present a new method for testing compatibility of candidate edges in the greedy triangulation, and new results on the rank of edges in various triangulations. Our edge test requires O(1) time for test and update, O(n) space, and O(n) time to initialize. Based on these results, we present fast greedy triangulation algorithms with expected case running time of O(n log n) for uniform distributions over convex regions. While algorithms with O(n) expected case running times exist, the algorithms presented here are simpler to implement and work well in practice.

Weconsiderthep-piercingproblem,inwhichwearegiven acollectionofregions,andwishtodeterminewhetherthere existsasetofppointsthatintersectseachofthegivenregions.Wegivelinearornear-linearalgorithmsforsmall valuesofpincaseswherethegivenregionsareeitheraxisparallelrectanglesorconvexc-orientedpolygonsintheplane (i.e.,convexpolygonswithsidesfromaxednitesetofdirections). Wealsoinvestigatetheplanarrectilinear(andpolygonal) p-centerproblem,inwhichwearegivenasetSofnpointsin theplane,andwishtondpaxis-parallelcongruentsquares (isotheticcopiesofsomegivenconvexpolygon,respectively) ofsmallestpossiblesizewhoseunioncoversS.Wealsostudy severalgeneralizationsoftheseproblems. Newresultsarealinear-timesolutionfortherectilinear3-centerproblem(byshowingthatthisproblemcan beformulatedasanLP-typeproblemandbyexhibitinga relationtoHellynumbers).WegiveO(nlogn)-timesolutionsfor4-piercingoftranslatesofasquare,aswellasfor therectilinear4-centerproblem;thisisworst-caseoptimal. WegiveO(npolylogn)-timesolutionsfor4-and5-piercing ofaxis-parallelrectangles,formoregeneralrectilinear4centerproblems,andforrectilinear5-centerproblems.2pierceabilityofasetofnconvexc-orientedpolygonscanbe decidedintimeO(c2nlogn),andthe2-centerproblemfor aconvexc-goncanbesolvedinO(c5nlogn)time.Therst solutionisworst-caseoptimalwhencisxed. BothauthorsacknowledgesupportbyG.I.F.|theGerman IsraeliFoundationforScienticResearchandDevelopment,and byaMaxPlanckResearchAward.WorkbyMichaSharirhasalso beensupportedbyNationalScienceFoundationGrantsCCR-94-

No abstract available.

Article Free Access Share on Fast greedy triangulation algorithms Authors: Matthew T. Dickerson Department of Mathematics and Computer Science, Middlebury College, Middlebury VT Department of Mathematics and Computer Science, Middlebury College, Middlebury VTView Profile , Robert L. Scot Drysdale Department of Mathematics and Computer Science, Dartmouth College, Hanover, NH Department of Mathematics and Computer Science, Dartmouth College, Hanover, NHView Profile , Scott A. McElfresh Department of Mathematics and Computer Science, Dartmouth College, Hanover, NH Department of Mathematics and Computer Science, Dartmouth College, Hanover, NHView Profile , Emo Welzl Institut für Informatik, Freie Universität Berlin Institut für Informatik, Freie Universität BerlinView Profile Authors Info & Claims SCG '94: Proceedings of the tenth annual symposium on Computational geometryJune 1994Pages 211–220https://doi.org/10.1145/177424.177649Published:10 June 1994Publication History 18citation883DownloadsMetricsTotal Citations18Total Downloads883Last 12 Months55Last 6 weeks12 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A halving hyperplane of a set S of n points in Rd 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 δn1/d, δ some constant. Such a set S is called dense.

The authors show that for every fixed $\delta > 0$ the following holds: If F is a union of n triangles, all of whose angles are at least $\delta $, then the complement of F has $O(n)$ connected components and the boundary of F consists of $O(n\log \log n)$ straight segments (where the constants of proportionality depend on $\delta $). This latter complexity becomes linear if all triangles are of roughly the same size or if they are all infinite wedges.

Let S be a set of n points in IR 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 O i 1 " d log fi d 1 " j , where fi 2 = 0, fi 3 = 1, and fi d 0:149 \\Delta 2 d\\Gamma1 (d \\Gamma 1)!, improving a previous bound of Alon et al. We present a deterministic algorithm for computing such a net in time n(1=") O(1) . We also consider two special cases: when S is in convex position, we prove the existence of a net of size O( 1 " log 1:6 1 " ); for 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=").

This paper presents the problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that $\Omega (\frac{1}{{d^2 }}) \leqslant R \leqslant \frac{{2\pi }}{d}$ for any graph. Moreover, it is proved that $R = \Theta (\frac{1}{d})$ for many graphs including planar graphs, complete graphs, hypercubes, multidimensional meshes and tori, and other special networks. It is also shown that the problem of deciding if $R = \frac{{2\pi }}{d}$ for a graph is NP-hard for $d = 4$, and by using a counting argument that $R = O(\frac{{\log d}}{{d^2 }})$ for many graphs.

We present a simple randomized algorithm which solves linear programs with n constraints and d variables in expected O(nde(d ln(n+1))1/4) time in the unit cost model (where we count the number of arithmetic operations on the numbers in the input). The expectation is over the internal randomizations performed by the algorithm, and holds for any input. The algorithm is presented in an abstract framework, which facilitates its application to several other related problems. The algorithm has been presented in a previous work by the authors [ShW], but its analysis and the subexponential complexity bound are new.

For compact Euclidean bodiesP, Q, we define λ(P, Q) to be the smallest ratior/s wherer > 0,s > 0 satisfy $$sQ' \subseteq P \subseteq rQ''$$ . HeresQ denotes a scaling ofQ by the factors, andQ′,Q″ are some translates ofQ. This function λ gives us a new distance function between bodies which, unlike previously studied measures, is invariant under affine transformations. If homothetic bodies are identified, the logarithm of this function is a metric. (Two bodies arehomothetic if one can be obtained from the other by scaling and translation.) For integerk ≥ 3, define λ(k) to be the minimum value such that for each convex polygonP there exists a convexk-gonQ with λ(P, Q) ≤ λ(k). Among other results, we prove that 2.118 ... <-λ(3) ≤ 2.25 and λ(k) = 1 + Θ(k −2). We give anO(n 2 log2 n)-time algorithm which, for any input convexn-gonP, finds a triangleT that minimizes λ(T, P) among triangles. However, in linear time we can find a trianglet with λ(t, P)<-2.25. Our study is motivated by the attempt to reduce the complexity of the polygon containment problem, and also the motion-planning problem. In each case we describe algorithms which run faster when certain implicitslackness parameters of the input are bounded away from 1. These algorithms illustrate a new algorithmic paradigm in computational geometry for coping with complexity.

It is shown that for every fixed delta >0 the following holds: if F is a union of n triangles, all of whose angles are at least delta , then the complement of F has O(n) connected components, and the boundary of F consists of O(n log log n) segments. This latter complexity becomes linear if all triangles are of roughly the same size or if they are all infinite wedges. A randomized algorithm that computes F in expected time O(n2/sup alpha (n)/ log n) is given. Several applications of these results are presented.>

Let (X, R) be a set system on an n-point set X. For a two-coloring on X, its discrepancy is defined as the maximum number by which the occurrences of the two colors differ in any set in R. It is shown that if for any m-point subset Y contained in X the number of distinct subsets induced by R on Y is bounded by O(m/sup d/) for a fixed integer d is a coloring with discrepancy bounded by O(n/sup 1/2-1/2d/ (log n)/sup 1+1/2d/). Also, if any subcollection of m sets of R partitions the points into at most O(m/sup d/) classes, then there is a coloring with discrepancy at most O(n/sup 1/2-1/2d/ n). These bounds imply improved upper bounds on the size of in -approximations for (X, R). All of the bounds are tight up to polylogarithmic factors in the worst case. The results allow the generalization of several results of J. Beck (1984) bounding the discrepancy in certain geometric settings to the case when the discrepancy is taken relative to an arbitrary measure.>

We present an algorithm to compute a Euclidean minimum spanning tree of a given set S of n points in @@@@d in time 𝒪(Τd(N, N) logd N), where Τd(n, m) is the time required to compute a bichromatic closest pair among n red and m blue points in @@@@d. If Τd(N, N) = Ω(N1+ε), for some fixed ε > 0, then the running time improves to 𝒪(Τd(N, N)). Furthermore, we describe a randomized algorithm to compute a bichromatic closest pair in expected time 𝒪((nm log n log m)2/3 + m log2 n + n log2 m) in @@@@3, which yields an 𝒪(N4/3 log4/3 N) expected time algorithm for computing a Euclidean minimum spanning tree of N points in @@@@3.

Article Free Access Share on Quasi-optimal upper bounds for simplex range searching and new zone theorems Authors: Bernard Chazelle Princeton University Princeton UniversityView Profile , Micha Sharir New York University and Tel Aviv University New York University and Tel Aviv UniversityView Profile , Emo Welzl Free University, Berlin Free University, BerlinView Profile Authors Info & Claims SCG '90: Proceedings of the sixth annual symposium on Computational geometryMay 1990 Pages 23–33https://doi.org/10.1145/98524.98532Online:01 May 1990Publication History 38citation18DownloadsMetricsTotal Citations38Total Downloads18Last 12 Months5Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my Alerts New Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

It is known that in general range spaces of VC-dimension d > 1 require ε-nets to be of size at least Ω(d/ε log 1/ε). We investigate the question whether this general lower bound is valid for the special range spaces that typically arise in computational geometry. We show that disks and pseudo-disks in the plane as well as halfspaces in R3 allow ε-nets of size only Ο(1/ε), which is best possible up to a multiplicative constant. The analogous questions for higher-dimensional spaces remain open.

The problem of drawing a graph in the plane so that edges appear as straight lines and the minimum angle formed by any pair of incident edges is maximized is studied. The resolution of a layout is defined to be the size of the minimum angle formed by incident edges of the graph, and the resolution of a graph is defined to be the maximum resolution of any layout of the graph. The resolution R of a graph is characterized in terms of the maximum node degree d of the graph by proving that Omega (1/d/sup 2/)>

Article Efficient parallel computation of arrangements of hyperplanes in d dimensions Share on Authors: Torben Hagerup Fachbereich 10, Informatik, Universität des Saarlandes, D-6600 Saarbrücken Fachbereich 10, Informatik, Universität des Saarlandes, D-6600 SaarbrückenView Profile , H. Jung Sektion Mathematik, Humboldt-Universität Berlin, PF 1297, DDR-1086, Berlin Sektion Mathematik, Humboldt-Universität Berlin, PF 1297, DDR-1086, BerlinView Profile , E. Welzl Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, D-1000 Berlin 33 Institut für Informatik, Fachbereich Mathematik, Freie Universität Berlin, Arnimallee 2-6, D-1000 Berlin 33View Profile Authors Info & Claims SPAA '90: Proceedings of the second annual ACM symposium on Parallel algorithms and architecturesMay 1990 Pages 290–297https://doi.org/10.1145/97444.97696Published:01 May 1990 4citation234DownloadsMetricsTotal Citations4Total Downloads234Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

A set A of n points in the plane has to be stored in such a way that for any query triangle t the number of points of A inside t can be computed efficiently. For this problem a solution is presented with Ο(√n log n) query time, Ο (n log n) space and Ο(n3/2 log n) preprocessing time. The constants in the asymptotic bounds are small, and the method is easy to implement.

An arrangement of n lines (or line segments) in the plane is the partition of the plane defined by these objects. Such an arrangement consists of Ο(n2) regions, called faces. In this paper we study the problem of calculating and storing arrangements implicitly, using subquadratic space and preprocessing, so that, given any query point p, we can calculate efficiently the face containing p. First, we consider the case of lines and show that with Λ(n) space1 and Λ(n3/2) preprocessing time, we can answer face queries in Λ(√n) + Ο(K) time, where K is the output size. (The query time is achieved with high probability.) In the process, we solve three interesting subproblems: 1) given a set of n 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 trade-off between increasing space and decreasing query time. Third, we extend our structure to report faces in an arrangement of line segments in Λ(n1/3) time, given Λ(n4/3) space and Λ(n5/3) preprocessing time.

Let S be a set of n non-intersecting line segments in the plane. The visibility graph GS of S is the graph that has the endpoints of the segments in S as nodes and in which two nodes are adjacent whenever they can “see” each other (i.e., the open line segment joining them is disjoint from all segments or is contained in a segment). Two new methods are presented to construct GS. Both methods are very simple to implement. The first method is based on a new solution to the following problem: given a set of points, for each point sort the other points around it by angle. It runs in time Ο(n2). The second method uses the fact that visibility graphs often are sparse and runs in time Ο(m log n) where m is the number of edges in GS. Both methods use only Ogr;(n) storage.

The range searching problems which allow partition trees where every query enters only a sublinear number of nodes are characterized as those with finite Vapnik - Chervonenk is dimension.

The authors study both the incidence counting and the many-faces problem for various kinds of curves, including lines, pseudolines, unit circles, general circles, and pseudocircles. They also extend the analysis to three dimensions, where they concentrate on the case of spheres, which is relevant for the three-dimensional unit-distance problem. They obtain upper bounds for certain quantities. The authors believe that the techniques they use are of independent interest.>

Article Partitioning and geometric embedding of range spaces of finite Vapnik-Chervonenkis dimension Share on Authors: N. Alon Department of Mathematics, Tel Aviv University, Ramat Aviv, TEL Aviv 69978, Israel Department of Mathematics, Tel Aviv University, Ramat Aviv, TEL Aviv 69978, IsraelView Profile , D. Haussler Computer Science Department, University of California at Santa Cruz, Santa Cruz, CA, USA Computer Science Department, University of California at Santa Cruz, Santa Cruz, CA, USAView Profile , E. Welzl Institutes for Information Processing, Technical University of Graz, Schiesstattgaser 4a, A-8010 GRAZ, Austria Institutes for Information Processing, Technical University of Graz, Schiesstattgaser 4a, A-8010 GRAZ, AustriaView Profile Authors Info & Claims SCG '87: Proceedings of the third annual symposium on Computational geometryOctober 1987 Pages 331–340https://doi.org/10.1145/41958.41994Online:01 October 1987Publication History 22citation296DownloadsMetricsTotal Citations22Total Downloads296Last 12 Months5Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access

No abstract available.

We present a new technique for half-space and simplex range query using Ο(n) space and Ο(na) query time, where a < d(d-1)/d(d-1) + 1 + γ for all dimensions d ≥ 2 and γ > 0. These bounds are better than those previously published for all d ≥ 2. The technique uses random sampling to build a partition-tree structure. We introduce the concept of an ε-net for an abstract set of ranges to describe the desired result of this random sampling and give necessary and sufficient conditions that a random sample is an ε-net with high probability. We illustrate the application of these ideas to other range query problems.

For H a set of lines in the Euclidean plane, $A(H)$ denotes the induced dissection, called the arrangement of H. We define the notion of a belt in $A(H)$, which is bounded by a subset of the edges in $A(H)$, and describe two algorithms for constructing belts. All this is motivated by applications to a host of seemingly unrelated problems including a type of range search and finding the minimum area triangle with the vertices taken from some finite set of points.

See figure1.1.for an example of a cut.A cut-3 sequence is a sequence of cuts such that, after the last cut we end with a piece that is the polygon P.

Graphs, regarded as grammar forms as well as coloring specifications, induce graph-families, so-called color-families. In this paper a minimal producer-graph for every color-family is introduced and as the main result it is shown that color-families are dense, in the sense that between any two families one can ‘squeeze in’ another one.