Search

In colored range counting (CRC), the input is a set of points where each point is assigned a "color" (or a "category") and the goal is to store them in a data structure such that the number of distinct categories inside a given query range can be counted efficiently. CRC has strong motivations as it allows data structure to deal with categorical data. However, colors (i.e., the categories) in the CRC problem do not have any internal structure, whereas this is not the case for many datasets in practice where hierarchical categories exist or where a single input belongs to multiple categories. Motivated by these, we consider variants of the problem where such structures can be represented. We define two variants of the problem called hierarchical range counting (HCC) and sub-category colored range counting (SCRC) and consider hierarchical structures that can either be a DAG or a tree. We show that the two problems on some special trees are in fact equivalent to other well-known problems in the literature. Based on these, we also give efficient data structures when the underlying hierarchy can be represented as a tree. We show a conditional lower bound for the general case when the existing hierarchy can be any DAG, through a reduction from the orthogonal vectors problem. [ABSTRACT FROM AUTHOR]

Given a set of n colored points with k colors in the plane, we study the problem of computing a maximum-width rainbow-bisecting empty annulus (of objects specifically axis-parallel square, axis-parallel rectangle and circle) problem. We call a region rainbow if it contains at least one point of each color. The maximum-width rainbow-bisecting empty annulus problem asks to find an annulus A of a particular shape with maximum possible width such that A does not contain any input points and it bisects the input point set into two parts, each of which is a rainbow. We compute a maximum-width rainbow-bisecting empty axis-parallel square, axis-parallel rectangular and circular annulus in O (n 3) time using O (n) space, in O (k 2 n 2 log ⁡ n) time using O (n log ⁡ n) space and in O (n 3) time using O (n 2) space respectively. [ABSTRACT FROM AUTHOR]

Let t > 1 be a real number. A geometric t -spanner is a geometric graph for a point set in R d with straight line segments between vertices such that the ratio of the shortest-path distance between every pair of vertices in the graph (with Euclidean edge lengths) to their actual Euclidean distance is at most t. An imprecise point set is modeled by a set R of regions in R d. If one chooses a point inside each region of R , then the resulting point set is called a precise instance from R. An imprecise t -spanner for an imprecise point set R is a graph G = (R , E) such that for each precise instance S from R , graph G S = (S , E S) , where E S is the set of edges corresponding to E and S , is a t -spanner. In this paper, we show an imprecise point set R of n straight-line segments in the plane such that any imprecise t -spanner for R has Ω (n 2) edges. Then, we give an algorithm that computes an imprecise t -spanner for a set of n pairwise disjoint d -dimensional balls with arbitrary sizes. This imprecise t -spanner has O (n / (t − 1) d) edges and can be computed in O (n log ⁡ n / (t − 1) d) time. Finally, we show that given an imprecise spanner, finding a precise instance such that its corresponding precise spanner has minimum dilation between all possible precise instances of the imprecise spanner is NP-hard, no matter if crossing edges are allowed or not. [ABSTRACT FROM AUTHOR]

Let S be a set of n geometric objects of constant complexity (e.g., points, line segments, disks, ellipses) in R 2 , and let ϱ : S × S → R ≥ 0 be a distance function on S. For a parameter r ≥ 0 , we define the proximity graph G (r) = (S , E) where E = { (e 1 , e 2) ∈ S × S | e 1 ≠ e 2 , ϱ (e 1 , e 2) ≤ r }. Given S , s , t ∈ S , and an integer k ≥ 1 , the reverse-shortest-path (RSP) problem asks for computing the smallest value r ⁎ ≥ 0 such that G (r ⁎) contains a path from s to t of length at most k. In this paper we present a general randomized technique that solves the RSP problem efficiently for a large family of geometric objects and distance functions. Using standard, and sometimes more involved, semi-algebraic range-searching techniques, we first give an efficient algorithm for the decision problem, namely, given a value r ≥ 0 , determine whether G (r) contains a path from s to t of length at most k. Next, we adapt our decision algorithm and combine it with a random-sampling method to compute r ⁎ , by efficiently performing a binary search over an implicit set of O (n 2) candidate 'critical' values that contains r ⁎. We illustrate the versatility of our general technique by applying it to a variety of geometric proximity graphs. For example, we obtain (i) an O ⁎ (n 4 / 3) expected-time randomized algorithm (where O ⁎ (⋅) hides polylog (n) factors) for the case where S is a set of (possibly intersecting) line segments in R 2 and ϱ (e 1 , e 2) = min x ∈ e 1 , y ∈ e 2 ⁡ ‖ x − y ‖ (where ‖ ⋅ ‖ is the Euclidean distance), and (ii) an O ⁎ (n + m 4 / 3) expected-time randomized algorithm for the case where S is a set of m points lying on an x -monotone polygonal chain T with n vertices, and ϱ (p , q) , for p , q ∈ S , is the smallest value h such that the points p ′ : = p + (0 , h) and q ′ : = q + (0 , h) are visible to each other, i.e., all points on the segment p ′ q ′ lie above or on the polygonal chain T. [ABSTRACT FROM AUTHOR]

We use the concept of production matrices to show that there exist sets of n points in the plane that admit Ω (42.11 n) crossing-free geometric graphs. This improves the previously best known bound of Ω (41.18 n) by Aichholzer et al. (2007). [ABSTRACT FROM AUTHOR]

Let P be a set of n points in R d where each point p ∈ P carries a weight drawn from a commutative monoid (M , + , 0). Given a d -rectangle r upd (i.e., an orthogonal rectangle in R d) and a value Δ ∈ M , a range update adds Δ to the weight of every point p ∈ P ∩ r upd ; given a d -rectangle r qry , a range sum query returns the total weight of the points in P ∩ r qry. The goal is to store P in a structure to support updates and queries with attractive performance guarantees. We describe a structure of O ˜ (n) space that handles an update in O ˜ (T upd) time and a query in O ˜ (T qry) time for arbitrary functions T upd (n) and T qry (n) satisfying T upd ⋅ T qry = n. The result holds for any fixed dimensionality d ≥ 2. Our query-update tradeoff is tight up to a polylog factor subject to the OMv-conjecture. [ABSTRACT FROM AUTHOR]

This paper addresses a family of geometric half-plane retrieval queries of points in the plane in the presence of geometric uncertainty. The problems include exact and uncertain point sets and half-plane queries defined by an exact or uncertain line whose location uncertainties are independent or dependent and are defined by k real-valued parameters. Point coordinate uncertainties are modeled with the Linear Parametric Geometric Uncertainty Model (LPGUM), an expressive and computationally efficient worst-case, first order linear approximation of geometric uncertainty that supports parametric dependencies between point locations. We present an efficient O (k 2) time and space algorithm for computing the envelope of the LPGUM line that defines the half-plane query. For an exact line and an LPGUM n points set, we present an O (log ⁡ n k + m k) time query and O (n k) space algorithm, where m is the number of LPGUM points on or above the half-plane line. For a LPGUM line and an exact points set, we present a O (k 2 + (k log ⁡ n log ⁡ log ⁡ n) ε + m) time and O ( n 2 log ⁡ n + k ε) space approximation algorithm, where 0 < ε ≤ 1 is the desired approximation error. For a LPGUM line and an LPGUM points set, we present two O (k 2 + (k log ⁡ n k log ⁡ log ⁡ n k) ε + m k) and O (m k 2 + (k log ⁡ n k log ⁡ log ⁡ n k) ε) time query and O ( (n k) 2 log ⁡ n k + k ε) space approximation algorithms for the independent and dependent case, respectively. [ABSTRACT FROM AUTHOR]

A set D of disks in the plane is said to be pierced by a point set P if each disk in D contains a point of P. Any set of pairwise intersecting unit disks can be pierced by 3 points (Hadwiger and Debrunner (1955) [7]). Stachó and independently Danzer established that any set of pairwise intersecting arbitrary disks can be pierced by 4 points (Stachó (1981–1984) [16]. Danzer (1986) [4]). Existing linear-time algorithms for finding a set of 4 or 5 points that pierce pairwise intersecting disks of arbitrary radius use the LP-type problem as a subroutine. We present simple linear-time algorithms for finding 3 points for piercing pairwise intersecting unit disks, and 5 points for piercing pairwise intersecting disks of arbitrary radius. Our algorithms use simple geometric transformations and avoid heavy machinery. We also show that 3 points are sometimes necessary for piercing pairwise intersecting unit disks. [ABSTRACT FROM AUTHOR]

Let P be a set of n points in the plane in general position, and consider the problem of finding an axis-parallel rectangle with a given perimeter, or area, or diagonal, that encloses the maximum number of points of P. We present an exact algorithm that finds such a rectangle in O (n 5 / 2 log ⁡ n) time, and, for the case of a fixed perimeter or diagonal, we also obtain (i) an improved exact algorithm that runs in O (n k 3 / 2 log ⁡ k) time, and (ii) an approximation algorithm that finds, in O (n + n k ε 5 log 5 / 2 ⁡ n k log ⁡ (1 ε log ⁡ n k)) time, a rectangle of the given perimeter that contains at least (1 − ε) k points of P , where k is the optimum value. We then show how to turn this algorithm into one that finds, for a given k , an axis-parallel rectangle of smallest perimeter (or area, or diagonal) that contains k points of P. We obtain the first subcubic algorithms for these problems, significantly improving the current state of the art. [ABSTRACT FROM AUTHOR]

We study an old geometric optimization problem in the plane. Given a perfect matching M on a set of n points in the plane, we can transform it to a non-crossing perfect matching by a finite sequence of flip operations. The flip operation removes two crossing edges from M and adds two non-crossing edges. Let f (M) and F (M) denote the minimum and maximum lengths of a flip sequence on M , respectively. It has been proved by Bonnet and Miltzow (2016) that f (M) = O (n 2) and by van Leeuwen and Schoone (1980) that F (M) = O (n 3). We prove that f (M) = O (n Δ) where Δ is the spread of the point set, which is defined as the ratio between the longest and the shortest pairwise distances. This improves the previous bound for point sets with sublinear spread. For a matching M on n points in convex position we prove that f (M) = n / 2 − 1 and F (M) = ( n / 2 2 ) ; these bounds are tight. Any bound on F (⋅) carries over to the bichromatic setting, while this is not necessarily true for f (⋅). Let M ′ be a bichromatic matching. The best known upper bound for f (M ′) is the same as for F (M ′) , which is essentially O (n 3). We prove that f (M ′) ⩽ n − 2 for points in convex position, and f (M ′) = O (n 2) for semi-collinear points. The flip operation can also be defined on spanning trees. For a spanning tree T on a convex point set we show that f (T) = O (n log ⁡ n). [ABSTRACT FROM AUTHOR]

This paper deals with constructing centralized geometric network that represents a set of clients that need to be connected to a server. We consider the problem of minimizing the sum of the shortest paths from the clients to the server in the network, subject to some constraints. We refer to this summation as the network cost. The motivation for this work was derived from the combination of centralized communication network and geometric sink spanner. Formally, given a set V of points (representing clients) in the plane, a special point q ∈ V (representing a server), a real number w > 0 (the network weight bound), and an integer h ≥ 1 (the hop bound), the goal is to construct a directed network G = (V , E) of minimum cost, such that there is a directed path from every point in V to q with at most h hops, and ∑ (v , u) ∈ E | v u | ≤ w , where | v u | denotes the Euclidean distance between v and u. In this paper we start by establishing a connection between the considered problem and geometric sink spanner network. Then, we present our main result, a bi-criteria approximation algorithm, that approximates both the weight and the cost of the network with respect to an optimal network, in (| V | / ε) O (h / ε). More precisely, we construct a network such that its cost (i.e., sum of the shortest paths from every v ∈ V to q) is at most (1 + h ε) times the cost of an optimal network and its weight (i.e., ∑ (v , u) ∈ E | v u |) is at most (1 + ε) ⋅ w , for any ε > 0. [ABSTRACT FROM AUTHOR]

Dilation of a set of points on the plane is the lowest possible dilation of a plane spanner on the point set. We show that dilation of vertices of any regular polygon is less than 1.4482. We introduce a method for constructing a triangulation of a regular polygon and prove this bound on its dilation. The upper bound on dilation is shown using mathematical proofs and experimental results. The new upper bound improves the previously known bound of 1.48454. [ABSTRACT FROM AUTHOR]

Abstract We consider sets L = { ℓ 1 , ... , ℓ n } of n labeled lines in general position in R 3 , and study the order types of point sets { p 1 , ... , p n } that stem from the intersections of the lines in L with (directed) planes Π, not parallel to any line of L , that is, the proper cross-sections of L. As two main results, we show that the number of different order types that can be obtained as cross-sections of L is O (n 9) when considering all possible planes Π, and O (n 3) when restricting considerations to sets of pairwise parallel planes, where both bounds are tight. The result for parallel planes implies that any set of n points in R 2 moving with constant (but possibly different) speeds along straight lines forms at most O (n 3) different order types over time. We further generalize the setting from R 3 to R d with d > 3 , showing that the number of order types that can be obtained as cross-sections of a set of n labeled (d − 2) -flats in R d with planes is O (( ( n 3 ) + n d (d − 2) )). [ABSTRACT FROM AUTHOR]

In this paper, we study two classic optimization problems: minimum geometric dominating set and set cover. In the dominating-set problem, for a given set of objects in the plane as input, the objective is to choose a minimum number of input objects such that every input object is dominated by the chosen set of objects. Here, we say that one object is dominated by another if their intersection is nonempty. For the second problem, for a given set of points and objects in the plane, the objective is to choose a minimum number of objects to cover all the points. This is a particular version of the set-cover problem. Both problems have been well-studied, subject to various restrictions on the input objects. These problems are APX -hard for object sets consisting of axis-parallel rectangles, ellipses, α -fat objects of constant description complexity, and convex polygons. On the other hand, PTAS s (polynomial time approximation schemes) are known for object sets consisting of disks or unit squares. Surprisingly, a PTAS was unknown even for arbitrary squares. For both problems obtaining a PTAS remains open for a large class of objects. For the dominating-set problem, we prove that a popular local-search algorithm leads to a (1 + ε) approximation for a family of homothets of a convex object (which includes arbitrary squares, k -regular polygons, translated and scaled copies of a convex set, etc.) in n O (1 / ε 2) time. On the other hand, the same approach leads to a PTAS for the geometric covering problem when the objects are convex pseudodisks (which include disks, unit height rectangles, homothetic convex objects, etc.). Consequently, we obtain an easy-to-implement approximation algorithm for both problems for a large class of objects, significantly improving the best-known approximation guarantees. [ABSTRACT FROM AUTHOR]

A geometric graph is a graph whose vertex set is a set of points in general position in the plane, and its edges are straight line segments joining these points. We show that for every integer k ≥ 2 , there exists a constant c > 0 such that the following holds. The edges of every dense geometric graph, with sufficiently many vertices, can be colored with k colors, such that the number of pairs of edges of the same color that cross is at most (1 / k − c) times the total number of pairs of edges that cross. The case when k = 2 and G is a complete geometric graph, was proved by Aichholzer et al. (2019) [2]. [ABSTRACT FROM AUTHOR]

We undertake a study on computing Hamiltonian alternating cycles and paths on bicolored point sets. This has been an intensively studied problem, not always with a solution, when the paths and cycles are also required to be plane. In this paper, we relax the constraint on the cycles and paths from being plane to being 1-plane, and deal with the same type of questions as those for the plane case, obtaining a remarkable variety of results. For point sets in general position, our main result is that it is always possible to obtain a 1-plane Hamiltonian alternating cycle. When the point set is in convex position, we prove that every Hamiltonian alternating cycle with minimum number of crossings is 1-plane, and provide O ( n ) and O ( n 2 ) time algorithms for computing, respectively, Hamiltonian alternating cycles and paths with minimum number of crossings. [ABSTRACT FROM AUTHOR]

We study an algorithmic problem that is motivated by ink minimization for sparse set visualizations. Our input is a set of points in the plane which are either blue, red, or purple. Blue points belong exclusively to the blue set, red points belong exclusively to the red set, and purple points belong to both sets. A red-blue-purple spanning graph (RBP spanning graph) is a set of edges connecting the points such that the subgraph induced by the red and purple points is connected, and the subgraph induced by the blue and purple points is connected. We study the geometric properties of minimum RBP spanning graphs and the algorithmic problems associated with computing them. Specifically, we show that the general problem can be solved in polynomial time using matroid techniques. In addition, we discuss more efficient algorithms for the case in which points are located on a line or a circle, and also describe a fast ( 1 2 ρ + 1 ) -approximation algorithm, where ρ is the Steiner ratio. [ABSTRACT FROM AUTHOR]

We study the cyclic color sequences induced at infinity by colored rays with apices being a given balanced finite bichromatic point set. We first study the case in which the rays are required to be pairwise disjoint. We derive a lower bound on the number of color sequences that can be realized from any such fixed point set and examine color sequences that can be realized regardless of the point set, exhibiting negative examples as well. We also provide a tight upper bound on the number of configurations that can be realized from a point set, and point sets for which there are asymptotically less configurations than that number. In addition, we provide algorithms to decide whether a color sequence is realizable from a given point set in a line or in general position. We address afterwards the variant of the problem where the rays are allowed to intersect. We prove that for some configurations and point sets, the number of ray crossings must be Θ ( n 2 ) and study then configurations that can be realized by rays that pairwise cross. We show that there are point sets for which the number of configurations that can be realized by pairwise-crossing rays is asymptotically smaller than the number of configurations realizable by pairwise-disjoint rays. We provide also point sets from which any configuration can be realized by pairwise-crossing rays and show that there is no configuration that can be realized by pairwise-crossing rays from every point set. [ABSTRACT FROM AUTHOR]

Let P be a finite point set in the plane. A c-ordinary triangle in P is a subset of P consisting of three non-collinear points such that each of the three lines determined by the three points contains at most c points of P . Motivated by a question of Erdős, and answering a question of de Zeeuw, we prove that there exists a constant c > 0 such that P contains a c -ordinary triangle, provided that P is not contained in the union of two lines. Furthermore, the number of c -ordinary triangles in P is Ω ( | P | ) . [ABSTRACT FROM AUTHOR]

Suppose that nk points in general position in the plane are colored red and blue, with at least n points of each color. We show that then there exist n pairwise disjoint convex sets, each of them containing k of the points, and each of them containing points of both colors. We also show that if P is a set of n ( d + 1 ) points in general position in R d colored by d colors with at least n points of each color, then there exist n pairwise disjoint d -dimensional simplices with vertices in P , each of them containing a point of every color. These results can be viewed as a step towards a common generalization of several previously known geometric partitioning results regarding colored point sets. [ABSTRACT FROM AUTHOR]

A unit-disk graph G (P) of a set P of points in the plane is a graph with P as its vertex set such that two points of P are connected by an edge if the distance between the two points is at most 1 and the weight of the edge is equal to the distance of the two points. Given P and a source point s ∈ P , we consider the problem of finding shortest paths in G (P) from s to all other vertices of G (P). In the L 2 case where the distance is measured by the L 2 metric, the problem has been extensively studied and the current best algorithm runs in O (n log 2 ⁡ n) time, with n = | P |. In this paper, we study the L 1 case in which the distance is measured under the L 1 metric (and each disk becomes a diamond); we present an O (n log ⁡ n) time algorithm, which matches the Ω (n log ⁡ n) -time lower bound. [ABSTRACT FROM AUTHOR]

A t -spanner is a subgraph of a graph G in which the length of the shortest path between two vertices never exceeds t times the length of the shortest path between them in G. A geometric graph is one whose vertices are points and whose edges are line segments between the corresponding points. Geometric t -spanners are t -spanners of the complete geometric graph on a given point set. Besides approximating the distance between points, we may ask a geometric t -spanner to be planar, have low degree, or low total edge length. One famous algorithm used to generate spanners is path-greedy , which scans pairs of vertices in non-decreasing order of edge length and adds the edge between them unless the current set of added edges already connects them with a path that t -approximates the edge length. Graphs from this algorithm are called path-greedy spanners. This work analyzes properties of path-greedy geometric spanners under different conditions. Specifically, we answer an open problem regarding the planarity and degree of path-greedy t -spanners for points in convex position in 2D. Further, we show a simple and efficient way to reduce the degree of a geometric spanner by adding extra points. [ABSTRACT FROM AUTHOR]

Spiral Galaxies is a pencil-and-paper puzzle played on a grid of unit squares: given a set of points called centers , the goal is to partition the grid into polyominoes such that each polyomino contains exactly one center and is 180 ∘ rotationally symmetric about its center. We show that this puzzle is NP-complete, ASP-complete, and #P-complete even if (a) all solutions to the puzzle have rectangles for polyominoes; or (b) the polyominoes are required to be rectangles and all solutions to the puzzle have just 1 × 1 , 1 × 3 , and 3 × 1 rectangles. The proof for the latter variant also implies NP/ASP/#P-completeness of finding a noncrossing perfect matching in distance-2 grid graphs where edges connect vertices of Euclidean distance 2. Moreover, we prove NP-completeness of the design problem of minimizing the number of centers such that there exists a set of galaxies that exactly cover a given shape. [ABSTRACT FROM AUTHOR]

An obstacle representation of a graph is a mapping of the vertices onto points in the plane and a set of connected regions of the plane (called obstacles) such that the straight-line segment connecting the points corresponding to two vertices does not intersect any obstacles if and only if the vertices are adjacent in the graph. Recently, Biedl and Mehrabi (Graph Drawing 2017) studied non-blocking grid obstacle representations of graphs in which the vertices of the graph are mapped onto points in the plane while the straight-line segments representing the adjacency between the vertices are replaced by the L 1 (Manhattan) shortest paths in the plane that avoid obstacles. In this paper, we introduce the notion of geodesic obstacle representations of graphs with the main goal of providing a generalized model, which comes naturally when viewing line segments as shortest paths in the Euclidean plane. To this end, we extend the definition of obstacle representation by allowing some obstacles-avoiding shortest path between the corresponding points in the underlying metric space whenever the vertices are adjacent in the graph. We consider both general and plane variants of geodesic obstacle representations (in a similar sense to obstacle representations) under any polyhedral distance function in R d as well as shortest path distances in graphs. Our results generalize and unify the notions of obstacle representations, plane obstacle representations and grid obstacle representations, leading to a number of questions on such representations. [ABSTRACT FROM AUTHOR]

A weighted bisector graph is a geometric graph whose faces are bounded by edges that are portions of multiplicatively weighted bisectors of pairs of (point) sites such that each of its faces is defined by exactly one site. A prominent example of a bisector graph is the multiplicatively weighted Voronoi diagram of a finite set of points which induces a tessellation of the plane into Voronoi faces bounded by circular arcs and straight-line segments. Several algorithms for computing various types of bisector graphs are known. In this paper we reverse the problem: Given a partition G of the plane into faces, find a set of points and suitable weights such that G is a bisector graph of the weighted points, if a solution exists. If G is a graph that is regular of degree three then we can decide in O (m) time whether it is a bisector graph, where m denotes the combinatorial complexity of G. In the same time we can identify up to two candidate solutions such that G could be their multiplicatively weighted Voronoi diagram. Additionally, we show that it is possible to recognize G as a multiplicatively weighted Voronoi diagram and find all possible solutions in O (m log ⁡ m) time if G is given by a set of disconnected lines and circles. [ABSTRACT FROM AUTHOR]

Given a set of n points in the plane, the Unit Disk Cover (UDC) problem asks to compute the minimum number of unit disks required to cover the points, along with a placement of the disks. The problem is NP-hard and several approximation algorithms have been designed over the last three decades. In this paper, we have engineered and experimentally compared practical performances of some of these algorithms on massive pointsets. The goal is to investigate which algorithms run fast and give good approximation in practice. We present a simple 7-approximation algorithm for UDC that runs in O (n) expected time and uses O (s) extra space, where s denotes the size of the generated cover. In our experiments, it turned out to be the speediest of all. We also present two heuristics to reduce the sizes of covers generated by it without slowing it down by much. To our knowledge, this is the first work that experimentally compares algorithms for the UDC problem. Experiments with them using massive pointsets (in the order of millions) throw light on their practical uses. We share the engineered algorithms via GitHub 1 for broader uses and future research in the domain of geometric optimization. [ABSTRACT FROM AUTHOR]

Two sets of labeled points { p 1 , ... , p n } and { q 1 , ... , q n } are of the same labeled order type if, for every i , j , k , the triples (p i , p j , p k) and (q i , q j , q k) have the same orientation. In the 1980's, Goodman, Pollack, and Sturmfels showed that (i) the number of labeled order types on n points is of order n 4 n + o (n) , (ii) all order types can be realized with double-exponential integer coordinates, and that (iii) certain order types indeed require double-exponential integer coordinates. In 2018, Caraballo, Díaz-Báñez, Fabila-Monroy, Hidalgo-Toscano, Leaños, and Montejano showed that at least n 3 n + o (n) labeled n -point order types can be realized on an integer grid of polynomial size. In this article, we improve their result by showing that at least n 4 n + o (n) labeled n -point order types can be realized on an integer grid of polynomial size, which is asymptotically tight in the exponent. Finally we conclude that there are n 3 n + o (n) order types in the unlabeled setting and that n 3 n + o (n) of them can be realized on an integer grid of polynomial size. [ABSTRACT FROM AUTHOR]

Bounded-angle (minimum) spanning trees were first introduced in the context of wireless networks with directional antennas. They are reminiscent of bounded-degree (minimum) spanning trees, which have received significant attention. Let P be a set of n points in the plane, and let 0 < α < 2 π be an angle. An α -spanning tree (α -ST) of P is a spanning tree of the complete Euclidean graph over P , with the following property: For each vertex p i ∈ P , the (smallest) angle that is spanned by all the edges incident to p i is at most α. An α -minimum spanning tree (α -MST) is an α -ST of P of minimum weight, where the weight of an α -ST is the sum of the lengths of its edges. In this paper, we consider the problem of computing an α -MST for the case where α = 2 π 3. We present a 4-approximation algorithm, thus improving upon the previous results of Aschner and Katz and Biniaz et al., who presented algorithms with approximation ratios 6 and 16 3 , respectively. To obtain this result, we devise an O (n) -time algorithm that, given any Hamiltonian path Π of P , constructs a 2 π 3 -ST T of P , such that T 's weight is at most twice that of Π and, moreover, T is a 3-hop spanner of Π. This latter result is optimal (with respect to T 's weight), since for any ε > 0 there exists a polygonal path for which every 2 π 3 -ST (of the corresponding set of points) has weight greater than 2 − ε times the weight of the path. [ABSTRACT FROM AUTHOR]

We consider a minimizing variant of the well-known No-Three-In-Line Problem , the Geometric Dominating Set Problem : What is the smallest number of points in an n × n grid such that every grid point lies on a common line with two of the points in the set? We show a lower bound of Ω (n 2 / 3) points and provide a constructive upper bound of size 2 ⌈ n / 2 ⌉. If the points of the dominating sets are required to be in general position we provide optimal solutions for grids of size up to 12 × 12. For arbitrary n the currently best upper bound for points in general position remains the obvious 2 n. Finally, we discuss the problem on the discrete torus where we prove an upper bound of O ((n log ⁡ n) 1 / 2). For n even or a multiple of 3, we can even show a constant upper bound of 4. We also mention a number of open questions and some further variations of the problem. [ABSTRACT FROM AUTHOR]

Let R be a set of n red points and B be a set of n blue points in the Euclidean plane. We study the problem of computing a planar drawing of a cycle of minimum length that contains vertices at points R ∪ B and alternates colors. When these points are collinear, we describe a Θ ( n log ⁡ n ) -time algorithm to find such a shortest alternating cycle where every edge has at most two bends. We extend our approach to compute shortest alternating paths in O ( n 2 ) time with two bends per edge and to compute shortest alternating cycles on 3-colored point sets in O ( n 2 ) time with O ( n ) bends per edge. We also prove that for arbitrary k -colored point sets, the problem of computing an alternating shortest cycle is NP-hard, where k is any positive integer constant. [ABSTRACT FROM AUTHOR]

We study a family of line segment visibility problems, related to classical art gallery problems, which are motivated by monitoring requirements in commercial data centers. Given a collection of non-overlapping line segments in the interior of a rectangle, and a requirement to monitor the segments from one side or the other, we examine the problem of finding a minimal set of point guards. Guards may be placed anywhere in the interior of the rectangle but not on a line segment. We consider combinatorial bounds of problem variants where the problem solver gets to decide which side of the segments to guard or the problem poser gets to decide which side to guard, and many others. We show that virtually all variants are NP-Hard to solve exactly, and then provide heuristics and experimental results to give insight into the associated practical problems. Finally we describe a program for using experiments to guide the search for optimal combinatorial bounds. [ABSTRACT FROM AUTHOR]

We consider the problem of computing the time-convex hull of a point set under the general L p metric in the presence of a straight-line highway in the plane. The traveling speed along the highway is assumed to be faster than that off the highway, and the shortest time-path between a distant pair may involve traveling along the highway. The time-convex hull TCH ( P ) of a point set P is the smallest set containing both P and all shortest time-paths between any two points in TCH ( P ) . In this paper we give an algorithm that computes the time-convex hull under the L p metric in optimal O ( n log ⁡ n ) time for a given set of n points and a real number p with 1 ≤ p ≤ ∞ . [ABSTRACT FROM AUTHOR]

We consider the problem of approximating the majority depth (Liu and Singh, 1993) of a point q with respect to an n -point set, S , by random sampling. At the heart of this problem is a data structures question: How can we preprocess a set of n lines so that we can quickly test whether a randomly selected vertex in the arrangement of these lines is above or below the median level. We describe a Monte Carlo data structure for this problem that can be constructed in O ( n log ⁡ n ) time, can answer queries in O ( ( log ⁡ n ) 4 / 3 ) expected time, and answers correctly with high probability. [ABSTRACT FROM AUTHOR]

Given two triangulations of a convex polygon, computing the minimum number of flips required to transform one to the other is a long-standing open problem. It is not known whether the problem is in P or NP-complete. We prove that two natural generalizations of the problem are NP-complete, namely computing the minimum number of flips between two triangulations of (1) a polygon with holes; (2) a set of points in the plane. [ABSTRACT FROM AUTHOR]

This paper defines and classifies the topology of the Steiner reducing set corresponding to a finite planar point set and its minimum weight triangulation. A Steiner point P is a Steiner reducing point of a planar point set X if the weight (sum of edge lengths) of a minimum weight triangulation of X ∪ { P } is less than that of X . The Steiner reducing set St ( X ) is the collection of all Steiner reducing points of X . We prove a structure theorem providing alternate geometric conditions for membership in the Steiner reducing set. We prove that St ( X ) can be topologically complex, containing multiple connected components or even holes. We construct families of sets X for which the number of connected components of St ( X ) grows linearly in the cardinality of X . Moreover, we prove that when St ( X ) is not simply connected, the rank of H 1 ( St ( X ) ) (i.e. the number of holes) can also grow linearly in the cardinality of X . Lastly, we give an example illustrating that the geometric conditions do not translate simply into conditions sufficient to completely characterize the Steiner reducing set. [ABSTRACT FROM AUTHOR]

We describe an algorithm that takes as input n points in the plane and a parameter ϵ , and produces as output an embedded planar graph having the given points as a subset of its vertices in which the graph distances are a ( 1 + ϵ ) -approximation to the geometric distances between the given points. For point sets in which the Delaunay triangulation has sharpest angle α , our algorithm's output has O ( β 2 ϵ n ) vertices, its weight is O ( β α ) times the minimum spanning tree weight where β = 1 α ϵ log ⁡ 1 α ϵ . The algorithm's running time, if a Delaunay triangulation is given, is linear in the size of the output. We use this result in a similarly fast deterministic approximation scheme for the traveling salesperson problem. [ABSTRACT FROM AUTHOR]

Given a set R of red points and a set B of blue points in the plane, we study the problem of determining all angles for which there exists an L-shape containing all points from B and no points from R . We propose a worst-case optimal algorithm to solve this problem in O ( n 2 ) time and O ( n ) storage, where n = | R | + | B | . We also describe an output-sensitive algorithm that reports these angles in O ( n 8 / 5 + ε + k log ⁡ k ) time and O ( n 8 / 5 + ε ) storage, where k is the number of reported angular intervals and ε > 0 is any fixed constant. [ABSTRACT FROM AUTHOR]

Let P be a set of n points in general position in the plane. In 1996, Urabe considered a partition of P into subsets S 1 ∪ ⋯ ∪ S l such that each S i forms a hole (or an empty convex polygon) of P and these holes are mutually disjoint. Let f ( P ) be the minimum number of holes over all such partitions of P and F ( n ) = max { f ( P ) } over all sets P of n points. Then the current best bounds are given by ⌈ n + 1 4 ⌉ ≤ F ( n ) ≤ ⌈ 5 n 18 ⌉ . In this paper, we prove that F ( n ) ≤ ⌈ n 4 ⌉ + 1 . [ABSTRACT FROM AUTHOR]

Given a set P of n points in the plane, Covering Points by Lines is the problem of finding a minimum-cardinality set L of lines such that every point p ∈ P is incident to some line ℓ ∈ L . As a geometric variant of Set Cover , Covering Points by Lines is still NP-hard. Moreover, it has been proved to be APX-hard, and hence does not admit any polynomial-time approximation scheme unless P = NP. In contrast to the small constant approximation lower bound implied by APX-hardness, the current best approximation ratio for Covering Points by Lines is still O ( log ⁡ n ) , namely the ratio achieved by the greedy algorithm for Set Cover . In this paper, we give a lower bound of Ω ( log ⁡ n ) on the approximation ratio of the greedy algorithm for Covering Points by Lines . We also study several related problems including Maximum Point Coverage by Lines , Minimum-Link Covering Tour , Minimum-Link Spanning Tour , and Min–Max-Turn Hamiltonian Tour . We show that all these problems are either APX-hard or at least NP-hard. In particular, our proof of APX-hardness of Min–Max-Turn Hamiltonian Tour sheds light on the difficulty of Bounded-Turn-Minimum-Length Hamiltonian Tour , a problem proposed by Aggarwal et al. at SODA 1997. [ABSTRACT FROM AUTHOR]

A bottleneck plane perfect matching of a set of n points in R 2 is defined to be a perfect non-crossing matching that minimizes the length of the longest edge; the length of this longest edge is known as bottleneck . The problem of computing a bottleneck plane perfect matching has been proved to be NP-hard. We present an algorithm that computes a bottleneck plane matching of size at least n 5 in O ( n log 2 ⁡ n ) -time. Then we extend our idea toward an O ( n log ⁡ n ) -time approximation algorithm which computes a plane matching of size at least 2 n 5 whose edges have length at most 2 + 3 times the bottleneck. [ABSTRACT FROM AUTHOR]

We consider an extension of the triangular-distance Delaunay graphs (TD-Delaunay) on a set P of points in general position in the plane. In TD-Delaunay, the convex distance is defined by a fixed-oriented equilateral triangle ▽, and there is an edge between two points in P if and only if there is an empty homothet of ▽ having the two points on its boundary. We consider higher-order triangular-distance Delaunay graphs, namely k -TD, which contains an edge between two points if the interior of the smallest homothet of ▽ having the two points on its boundary contains at most k points of P . We consider the connectivity, Hamiltonicity and perfect-matching admissibility of k -TD. Finally we consider the problem of blocking the edges of k -TD. [ABSTRACT FROM AUTHOR]

The family of Θ k -graphs is an important class of sparse geometric spanners with a small spanning ratio. Although they are a well-studied class of geometric graphs, no bound is known on the spanning and routing ratios of the directed Θ 6 -graph. We show that the directed Θ 6 -graph of a point set P , denoted Θ → 6 (P) , is a 7-spanner and there exist point sets where the spanning ratio is at least 4 − ε , for any ε > 0. It is known that the standard greedy Θ-routing algorithm may have an unbounded routing ratio on Θ → 6 (P). We design a simple, online, local, memoryless routing algorithm on Θ → 6 (P) whose routing ratio is at most 8 and show that no algorithm can have a routing ratio better than 6 − ε. [ABSTRACT FROM AUTHOR]

A triangle T ′ is ε -similar to another triangle T if their angles pairwise differ by at most ε. Given a triangle T , ε > 0 and n ∈ N , Bárány and Füredi asked to determine the maximum number of triangles h (n , T , ε) being ε -similar to T in a planar point set of size n. We show that for almost all triangles T there exists ε = ε (T) > 0 such that h (n , T , ε) = (1 + o (1)) n 3 / 24. Exploring connections to hypergraph Turán problems, we use flag algebras and stability techniques for the proof. [ABSTRACT FROM AUTHOR]

Given a set P of n points and a set S of m weighted disks in the plane, the disk coverage problem asks for a subset of disks of minimum total weight that cover all points of P. The problem is NP-hard. In this paper, we consider a line-constrained version in which all disks are centered on a line L (while points of P can be anywhere in the plane). We present an O ((m + n) log ⁡ (m + n) + κ log ⁡ m) time algorithm for the problem, where κ is the number of pairs of disks whose boundaries intersect. Alternatively, we can also solve the problem in O (n m log ⁡ (m + n)) time. For the unit-disk case where all disks have the same radius, the running time can be reduced to O ((n + m) log ⁡ (m + n)). In addition, we solve in O ((m + n) log ⁡ (m + n)) time the L ∞ and L 1 cases of the problem, in which the disks are squares and diamonds, respectively. We further demonstrate that our techniques can also be used to solve other geometric coverage problems. For example, given in the plane a set P of n points and a set S of n weighted half-planes, we solve in O (n 4 log ⁡ n) time the problem of finding a subset of half-planes to cover P so that their total weight is minimized. This improves the previous best algorithm of O (n 5) time by almost a linear factor. If all half-planes are lower ones, then our algorithm runs in O (n 2 log ⁡ n) time, which improves the previous best algorithm of O (n 4) time by almost a quadratic factor. [ABSTRACT FROM AUTHOR]

Let S = R ∪ B be a point set in the plane in general position such that each of its elements is colored either red or blue, where R and B denote the points colored red and the points colored blue, respectively. A quadrilateral with vertices in S is called a 4-hole if its interior is empty of elements of S . We say that a 4-hole of S is balanced if it has 2 red and 2 blue points of S as vertices. In this paper, we prove that if R and B contain n points each then S has at least n 2 − 4 n 12 balanced 4-holes, and this bound is tight up to a constant factor. Since there are two-colored point sets with no balanced convex 4-holes, we further provide a characterization of the two-colored point sets having this type of 4-holes. [ABSTRACT FROM AUTHOR]

In this paper we determine the exact stretch factor of L ∞ -Delaunay triangulations of points in the plane. We do this not only when the distance between the points is defined by the usual L 2 -metric but also when it is defined by the L p -metric, for any p ∈ [ 1 , ∞ ] . We then apply this result to compute the exact stretch factor of L 1 -Delaunay triangulations when the distance between the points is defined by the L 1 -, L ∞ -, or L 2 -metric. In the important case of the L 2 -metric, we obtain that the stretch factor of L 1 -Delaunay and L ∞ -Delaunay triangulations is exactly 4 + 2 2 ≈ 2.61 . This is the first time that the stretch factor of an L p -Delaunay triangulation, for any p ∈ [ 1 , ∞ ] , is determined exactly. We show, in particular, how to construct between any two points a and b of an L 1 -Delaunay or L ∞ -Delaunay triangulation a path whose length is no more than 4 + 2 2 times the Euclidean distance between a and b . This improves the bound of 10 by Chew (SoCG '86) [5] . We also describe families of point sets whose L 1 -Delaunay or L ∞ -Delaunay triangulation has a stretch factor that can be made arbitrarily close to 4 + 2 2 . [ABSTRACT FROM AUTHOR]

Given a set of points in the plane, we show that the θ -graph with 5 cones is a geometric spanner with spanning ratio at most 50 + 22 5 ≈ 9.960 . This is the first constant upper bound on the spanning ratio of this graph. The upper bound uses a constructive argument that gives a (possibly self-intersecting) path between any two vertices, of length at most 50 + 22 5 times the Euclidean distance between the vertices. We also give a lower bound on the spanning ratio of 1 2 ( 11 5 − 17 ) ≈ 3.798 . [ABSTRACT FROM AUTHOR]

We study a class of geometric optimization problems closely related to the 2-center problem: Given a set S of n pairs of points in the plane, for every pair, we want to assign red color to a point of the pair and blue color to the other point in order to optimize the radii of the minimum enclosing ball of the red points and the minimum enclosing ball of the blue points. In particular, we consider the problems of minimizing the maximum and minimizing the sum of the two radii of the minimum enclosing balls. For each case, minmax and minsum, we consider distances measured in the L 2 and in the L ∞ metrics. [ABSTRACT FROM AUTHOR]

Given a set of points P and axis-aligned rectangles R in the plane, a point p ∈ P is called exposed if it lies outside all rectangles in R. In the max-exposure problem , given an integer parameter k , we want to delete k rectangles from R so as to maximize the number of exposed points. We show that the problem is NP -hard and assuming plausible complexity conjectures is also hard to approximate even when rectangles in R are translates of two fixed rectangles. However, if R only consists of translates of a single rectangle, we present a polynomial-time approximation scheme. For range space defined by general rectangles, we present a simple O (k) bicriteria approximation algorithm; that is by deleting O (k 2) rectangles, we can expose at least Ω (1 / k) of the optimal number of points. [ABSTRACT FROM AUTHOR]

We study the Tukey layers and convex layers of a planar point set, which consists of n points independently and uniformly sampled from a convex polygon with k vertices. We show that the expected number of vertices on the first t Tukey layers is O (k t log ⁡ (n / k)) and the expected number of vertices on the first t convex layers is O (k t 3 log ⁡ (n / (k t 2))). We also show a lower bound of Ω (t log ⁡ n) for both quantities in the special cases where k = 3 , 4. The implications of those results in the average-case analysis of two computational geometry algorithms are then discussed. [ABSTRACT FROM AUTHOR]