Skip to Content

Instrukcja korzystania z Biblioteki

Serwisy:

Ukryty Internet | Wyszukiwarki specjalistyczne tekstów i źródeł naukowych | Translatory online | Encyklopedie i słowniki online

Translator:

Kosmos
Astronomia Astrofizyka
Inne

Kultura
Sztuka dawna i współczesna, muzea i kolekcje

Metoda
Metodologia nauk, Matematyka, Filozofia, Miary i wagi, Pomiary

Materia
Substancje, reakcje, energia
Fizyka, chemia i inżynieria materiałowa

Człowiek
Antropologia kulturowa Socjologia Psychologia Zdrowie i medycyna

Wizje
Przewidywania Kosmologia Religie Ideologia Polityka

Ziemia
Geologia, geofizyka, geochemia, środowisko przyrodnicze

Życie
Biologia, biologia molekularna i genetyka

Cyberprzestrzeń
Technologia cyberprzestrzeni, cyberkultura, media i komunikacja

Działalność
Wiadomości | Gospodarka, biznes, zarządzanie, ekonomia

Technologie
Budownictwo, energetyka, transport, wytwarzanie, technologie informacyjne

Journal of Computational Geometry

We define a simple orthogonal polyhedron to be a three-dimensional polyhedron with the topology of a sphere in which three mutually-perpendicular edges meet at each vertex.By analogy to Steinitz's theorem characterizing the graphs of convex polyhedra, we find graph-theoretic characterizations of three classes of simple orthogonal polyhedra: corner polyhedra, which can be drawn by isometric projection in the plane with only one hidden vertex, xyz polyhedra, in which each axis-parallel line through a vertex contains exactly one other vertex, and arbitrary simple orthogonal polyhedra. In particular, the graphs of xyz polyhedra are exactly the bipartite cubic polyhedral graphs, and every bipartite cubic polyhedral graph with a 4-connected dual graph is the graph of a corner polyhedron. Based on our characterizations we find efficient algorithms for constructing orthogonal polyhedra from their graphs.

http://jocg.org/index.php/jocg/article/view/129 2014/09/16 - 23:31

We obtain a polynomial time approximation scheme for the terrain guarding problem improving upon several recent constant factor approximations. Our algorithm is a local search algorithm inspired by the recent results of Chan and Har-Peled (SoCG 2009) and Mustafa and Ray (DCG 2010). Our key contribution is to show the existence of a planar graph that appropriately relates the local and global optimum.

http://jocg.org/index.php/jocg/article/view/128 2014/05/31 - 16:00

Can folding a piece of paper flat make it larger? We explore whether a shape S must be scaled to cover a flat-folded copy of itself. We consider both single folds and arbitrary folds (continuous piecewise isometries \(S\to\mathbb{R}^2\)). The underlying problem is motivated by computational origami, and is related to other covering and fixturing problems, such as Lebesgue’s universal cover problem and force closure grasps. In addition to considering special shapes (squares, equilateral triangles, polygons and disks), we give upper and lower bounds on scale factors for single folds of convex objects and arbitrary folds of simply connected objects.

http://jocg.org/index.php/jocg/article/view/160 2014/05/13 - 05:55

Let S be a set of n points in Rd. A Steiner convex partition is a tiling of conv(S) with empty convex bodies. For every integer d, we show that S admits a Steiner convex partition with at most ⌈(n-1)/d⌉ tiles. This bound is the best possible for points in general position in the plane, and it is the best possible apart from constant factors in every fixed dimension d≥3. We also give the first constant-factor approximation algorithm for computing a minimum Steiner convex partition of a planar point set in general position. Establishing a tight lower bound for the maximum volume of a tile in a Steiner convex partition of any n points in the unit cube is equivalent to a famous problem of Danzer and Rogers. It is conjectured that the volume of the largest tile is ω(1/n). Here we give a (1-ε)-approximation algorithm for computing the maximum volume of an empty convex body amidst n given points in the d-dimensional unit box [0,1]d.

http://jocg.org/index.php/jocg/article/view/112 2014/05/06 - 21:08

How must n equal circles of given radius be placed so that they cover as great a part of the area of the unit circle as possible? To analyse this mathematical problem, mechanical models are introduced. A generalized tensegrity structure is associated with a maximum area configuration of the n circles, whose equilibrium configuration is determined numerically with the method of dynamic relaxation, and the stability of equilibrium is investigated by means of the stiffness matrix of the tensegrity structure. In this Part I, the principles of the models are presented, while an application will be shown in the forthcoming Part II.

http://jocg.org/index.php/jocg/article/view/108 2014/05/06 - 21:08

How must n equal circles of given radius r be placed so that they cover as great a part of the area of the unit circle as possible? In this Part II of a two-part paper, a conjectured solution of this problem for n = 5 is given for r varying from the maximum packing radius to the minimum covering radius. Results are obtained by applying a mechanical model described in Part I. A generalized tensegrity structure is associated with a maximum area configuration of the 5 circles, and by using catastrophe theory, it is pointed out that the ''equilibrium paths'' have bifurcations, that is, at certain values of r, the type of the tensegrity structure and so the type of the circle configuration changes.

http://jocg.org/index.php/jocg/article/view/109 2014/05/06 - 21:08

We study Delaunay complexes and Voronoi diagrams in the Poincaré ball, a conformal model of the hyperbolic space, in any dimension. We elaborate on our earlier work on the space of spheres [CCCG'92], giving a detailed description of algorithms. We also study algebraic and arithmetic issues, observing that only rational computations are needed. All proofs are based on geometric reasoning; they do not resort to any use of the analytic formula of the hyperbolic distance. This allows for an exact and efficient implementation in 2D. All degenerate cases are handled. The implementation will be submitted to the CGAL editorial board for future integration into the CGAL library.

http://jocg.org/index.php/jocg/article/view/141 2014/03/20 - 21:51

We study Delaunay complexes and Voronoi diagrams in the Poincaré ball, a conformal model of the hyperbolic space, in any dimension. We elaborate on our earlier work on the space of spheres [CCCG'92], giving a detailed description of algorithms. We also study algebraic and arithmetic issues, observing that only rational computations are needed. All proofs are based on geometric reasoning; they do not resort to any use of the analytic formula of the hyperbolic distance. This allows for an exact and efficient implementation in 2D. All degenerate cases are handled. The implementation will be submitted to the CGAL editorial board for future integration into the CGAL library.

http://jocg.org/index.php/jocg/article/view/141 2014/03/20 - 21:51

For \(k\ge 3\), a \(k\)-angulation is a 2-connected plane graph in which every internal face is a \(k\)-gon. We say that a point set \(P\) admits a plane graph \(G\) if there is a straight-line drawing of \(G\) that maps \(V(G)\) onto \(P\) and has the same facial cycles and outer face as \(G\). We investigate the conditions under which a point set \(P\) admits a \(k\)-angulation and find that, for sets containing at least \(2k^2\) points, the only obstructions are those that follow from Euler’s formula.

http://jocg.org/index.php/jocg/article/view/92 2014/03/08 - 04:16

A polygon \(Q\) is a \(k\)-bounded Hausdorff Core of a polygon \(P\) if \(P\) contains \(Q\), \(Q\) is convex, and the Hausdorff distance between \(P\) and \(Q\) is at most \(k\). A Hausdorff Core of \(P\) is a \(k\)-bounded Hausdorff Core of \(P\) with the minimum possible value of \(k\), which we denote \(k_{\min}\). Given any \(k\) and any \(\varepsilon\gt 0\), we describe an algorithm for computing a \(k'\)-bounded Hausdorff Core (if one exists) in \(O(n^3+n^2\varepsilon^{-4}(\log n+ \varepsilon^{-2}))\) time, where \(k'\lt k+d_{\text{rad}}\cdot\varepsilon\) and \(d_{\text{rad}}\) is the radius of the smallest disc that encloses \(P\) and whose center is in \(P\). We use this solution to provide an approximation algorithm for the optimization Hausdorff Core problem which results in a solution of size \(k_{\min}+d_{\text{rad}}\cdot\varepsilon\) in \(O(\log(\varepsilon^{-1})(n^3+n^2\varepsilon^{-4}(\log n+ \varepsilon^{-2})))\) time. Finally, we describe an approximation scheme for the \(k\)-bounded Hausdorff Core problem which, given a polygon \(P\), a distance \(k\), and any \(\varepsilon\gt 0\), answers true if there is a \(((1+\varepsilon)k)\)-bounded Hausdorff Core and false if there is no \(k\)-bounded Hausdorff Core. The running time of the approximation scheme is in \(O(n^3+n^2\varepsilon^{-4}(\log n+ \varepsilon^{-2}))\).

http://jocg.org/index.php/jocg/article/view/127 2014/02/17 - 17:06

Let D be a set of n pairwise disjoint unit disks in the plane. We describe how to build a data structure for D so that for any point set P containing exactly one point from each disk, we can quickly find the onion decomposition (convex layers) of P.Our data structure can be built in O(n log n) time and has linear size. Given P, we can find its onion decomposition in O(n log k) time, where k is the number of layers. We also provide a matching lower bound. Our solution is based on a recursive space decomposition, combined with a fast algorithm to compute the union of two disjoint onion decompositions.

http://jocg.org/index.php/jocg/article/view/140 2014/01/15 - 13:06

We prove that for any point set P in the plane, a triangle T, and a positive integer k, there exists a coloring of P with k colors such that any homothetic copy of T containing at least 144k8 points of P contains at least one of each color. This is the first polynomial bound for range spaces induced by homothetic polygons.The only previously known bound for this problem applies to the more general case of octants in ℝ3, but is doubly exponential.

http://jocg.org/index.php/jocg/article/view/136 2013/12/23 - 20:31

Consider the continuum of points along the edges of a network, i.e., an undirected graph with positive edge weights. We measure distance between these points in terms of the shortest path distance along the network, known as the network distance. Within this metric space, we study farthest points.We introduce network farthest-point diagrams, which capture how the farthest points---and the distance to them---change as we traverse the network. We preprocess a network G such that, when given a query point q on G, we can quickly determine the farthest point(s) from q in G as well as the farthest distance from q in G. Furthermore, we introduce a data structure supporting queries for the parts of the network that are farther away from q than some threshold R > 0, where R is part of the query.We also introduce the minimum eccentricity feed-link problem defined as follows. Given a network G with geometric edge weights and a point p that is not on G, connect p to a point q on G with a straight line segment pq, called a feed-link, such that the largest network distance from p to any point in the resulting network is minimized. We solve the minimum eccentricity feed-link problem using eccentricity diagrams. In addition, we provide a data structure for the query version, where the network G is fixed and a query consists of the point p.

http://jocg.org/index.php/jocg/article/view/131 2013/12/20 - 09:10

Let T be a rooted and weighted tree, where the weight of any node is equal to the sum of the weights of its children. The popular Treemap algorithm visualizes such a tree as a hierarchical partition of a square into rectangles, where the area of the rectangle corresponding to any node in T is equal to the weight of that node. The aspect ratio of the rectangles in such a rectangular partition necessarily depends on the weights and can become arbitrarily high.We introduce a new hierarchical partition scheme, called a polygonal partition, which uses convex polygons rather than just rectangles. We present two methods for constructing polygonal partitions, both having guarantees on the worst-case aspect ratio of the constructed polygons; in particular, both methods guarantee a bound on the aspect ratio that is independent of the weights of the nodes.We also consider rectangular partitions with slack, where the areas of the rectangles may differ slightly from the weights of the corresponding nodes. We show that this makes it possible to obtain partitions with constant aspect ratio. This result generalizes to hyper-rectangular partitions in ℝd. We use these partitions with slack for embedding ultrametrics into d-dimensional Euclidean space:  we give a polylog(Δ)-approximation algorithm for embedding n-point ultrametrics into ℝd with minimum distortion, where Δ denotes the spread of the metric. The previously best-known approximation ratio for this problem was polynomial in n. This is the first algorithm for embedding a non-trivial family of weighted-graph metrics into a space of constant dimension that achieves polylogarithmic approximation ratio.

http://jocg.org/index.php/jocg/article/view/74 2013/12/20 - 09:10

We study the properties of affine rigidity of a hypergraph and prove a variety of fundamental results. First, we show that affine rigidity is a generic property (i.e., depends only on the hypergraph, not the particular embedding). Then we prove that a graph is generically neighborhood affinely rigid in d-dimensional space if it is (d+1)-vertex-connected. We also show neighborhood affine rigidity of a graph implies universal rigidity of its squared graph.  Our results, and affine rigidity more generally, have natural applications in point registration and localization, as well as connections to manifold learning.

http://jocg.org/index.php/jocg/article/view/49 2013/12/10 - 22:00

We study the multiscale simplicial flat norm (MSFN) problem, which computes flat norm at various scales of sets defined as oriented subcomplexes of finite simplicial complexes in arbitrary dimensions. We show that MSFN is NP-complete when homology is defined over integers. We cast MSFN as an instance of integer linear optimization. Following recent results on related problems, the MSFN integer program can be solved in polynomial time by solving its linear programming relaxation, when the simplicial complex satisfies a simple topological condition (absence of relative torsion). Our most significant contribution is the simplicial deformation theorem, which states that one may approximate a general current with a simplicial current while bounding the expansion of its mass. We present explicit bounds on the quality of this approximation, which indicate that the simplicial current gets closer to the original current as we make the simplicial complex finer. MSFN opens up the possibilities of using flat norm to denoise or extract scale information of large data sets in arbitrary dimensions. On the other hand, it allows one to employ the large body of algorithmic results on simplicial complexes to address more general problems related to currents.

http://jocg.org/index.php/jocg/article/view/85 2013/11/12 - 22:09

The k-means method is the method of choice for clustering large-scale data sets and it performs exceedingly well in practice despite its exponential worst-case running-time. To narrow the gap between theory and practice, k-means has been studied in the semi-random input model of smoothed analysis, which often leads to more realistic conclusions than mere worst-case analysis. For the case that n data points in Rd are perturbed by Gaussian noise with standard deviation σ, it has been shown that the expected running-time is bounded by a polynomial in n and 1/σ. This result assumes that squared Euclidean distances are used as the distance measure.In many applications, however, data is to be clustered with respect to Bregman divergences rather than squared Euclidean distances. A prominent example is the Kullback-Leibler divergence (a.k.a. relative entropy) that is commonly used to cluster web pages. To broaden the knowledge about this important class of distance measures, we analyze the running-time of the k-means method for Bregman divergences. We first give a smoothed analysis of k-means with (almost) arbitrary Bregman divergences, and we show bounds of poly(nk, 1/σ) and kkd·poly(n, 1/σ). The latter yields a polynomial bound if k and d are small compared to n. On the other hand, we show that the exponential lower bound carries over to a huge class of Bregman divergences.

http://jocg.org/index.php/jocg/article/view/39 2013/07/23 - 16:02

Let A1,A2,…,An be the vertices of a polygon with unit perimeter, that is Σi |Ai Ai+1|=1. We derive various tight estimates on the minimum and maximum values of the sum of pairwise distances, and respectively sum of pairwise squared distances among its vertices. In most cases such estimates on these sumsin the literature were known only for convex polygons.In the second part, we turn to a problem of Braß  regarding the maximum perimeter of a simple n-gon (n odd) contained in a disk of unit radius. The problem was recently solved by Audet et al. 2009, who gave an exact formula. Here we present an alternative simpler proof of this formula. We then examine what happens if the simplicity condition is dropped, and obtain an exact formula for the maximum perimeter in this case as well.

http://jocg.org/index.php/jocg/article/view/45 2013/07/04 - 10:57

Let A1,A2,…,An be the vertices of a polygon with unit perimeter, that is Σi |Ai Ai+1|=1. We derive various tight estimates on the minimum and maximum values of the sum of pairwise distances, and respectively sum of pairwise squared distances among its vertices. In most cases such estimates on these sumsin the literature were known only for convex polygons.In the second part, we turn to a problem of Braß  regarding the maximum perimeter of a simple n-gon (n odd) contained in a disk of unit radius. The problem was recently solved by Audet et al. 2009, who gave an exact formula. Here we present an alternative simpler proof of this formula. We then examine what happens if the simplicity condition is dropped, and obtain an exact formula for the maximum perimeter in this case as well.

http://jocg.org/index.php/jocg/article/view/45 2013/07/04 - 10:57

We study water flow computation on imprecise terrains. We consider two approaches to modeling flow on a terrain: one where water flows across the surface of a polyhedral terrain in the direction of steepest descent, and one where water only flows along the edges of a predefined graph, for example a grid or a triangulation. In both cases each vertex has an imprecise elevation, given by an interval of possible values, while its (x,y)-coordinates are fixed. For the first model, we show that the problem of deciding whether one vertex may be contained in the watershed of another is NP-hard. In contrast, for the second model we give a simple O(n log n) time algorithm to compute the minimal and the maximal watershed of a vertex, or a set of vertices, where n is the number of edges of the graph. On a grid model, we can compute the same in O(n) time.

http://jocg.org/index.php/jocg/article/view/82 2013/06/26 - 14:09

A rectangular partition is the partition of an (axis-aligned) rectangle into interior-disjoint rectangles. We ask whether a rectangular partition permits a nice drawing of its dual, that is, a straight-line embedding of it such that each dual vertex is placed into the rectangle that it represents. We show that deciding whether such a drawing exists is NP-complete. Moreover, we consider the drawing where a vertex is placed in the center of the representing rectangle and consider sufficient conditions for this drawing to be nice. This question is studied both in the plane and for the higher-dimensional generalization of rectangular partitions.

http://jocg.org/index.php/jocg/article/view/104 2013/03/24 - 18:26

Erdős conjectured in 1946 that every n-point set P in convex position in the plane contains a point that determines at least ⌊n/2⌋ distinct distances to the other points of P. The best known lower bound due to Dumitrescu (2006) is 13n/36 - O(1). In the present note, we slightly improve on this result to (13/36 + ε)n - O(1) for ε ≈ 1/23000. Our main ingredient is an improved bound on the maximum number of isosceles triangles determined by P.

http://jocg.org/index.php/jocg/article/view/103 2013/03/22 - 04:03

Over the past decade, the kinetic-data-structures framework has become thestandard in computational geometry for dealing with moving objects. A fundamental assumption underlying the framework is that the motions of the objects are known in advance. This assumption severely limits the applicability of KDSs. We study KDSs in the black-box model, which is a hybrid of the KDS model and the traditional time-slicing approach. In this more practical model we receive the position of each object at regular time steps and we have an upper bound on dmax, the maximum displacement of any point in one time step.We study the maintenance of the convex hull and the Delaunay triangulation of a planar point set P in the black-box model, under the following assumption on dmax: there is some constant k such that for any point p in P the disk of radius dmax contains at most k points. We analyze our algorithms in terms of Δk, the so-called k-spread of P. We show how to update the convex hull at each time step in O(min(nkΔklog n)log n) amortized time. For the Delaunay triangulation our main contribution is an analysis of the standard edge-flipping approach; we show that the number of flips is O(k2Δk2) at each time step.

http://jocg.org/index.php/jocg/article/view/89 2012/12/30 - 23:29

Let S be a set of n points in Rd and let t>1 be a real number. A graph G=(S,E) is called a t-spanner for S, if for any two points p and q in S, the shortest-path distance in G between p and q is at most t|pq|, where |pq| denotes the Euclidean distance between p and q. The graph G is called θ-angle-constrained, if any two distinct edges sharing an endpoint make an angle of at least θ. It is shown that, for any θ with 0<θ<π/3$, a θ-angle-constrained t-spanner can be computed in O(nlog n) time, where t depends only on θ. For values of θ approaching 0, we have t=1 + O(θ).

http://jocg.org/index.php/jocg/article/view/94 2012/11/13 - 22:59

For a variety of regularized optimization problems in machine learning, algorithms computing the entire solution path have been developed recently. Most of these methods are quadratic programs that are parameterized by a single parameter, as for example the Support Vector Machine (SVM). Solution path algorithms do not only compute the solution for one particular value of the regularization parameter but the entire path of solutions, making the selection of an optimal parameter much easier.It has been assumed that these piecewise linear solution paths have only linear complexity, i.e. linearly many bends. We prove that for the support vector machine this complexity can be exponential in the number of training points in the worst case. More strongly, we construct a single instance of n input points in d dimensions for an SVM such that at least Θ(2n/2) = Θ(2d) many distinct subsets of support vectors occur as the regularization parameter changes.

http://jocg.org/index.php/jocg/article/view/88 2012/10/25 - 22:57

Polyomino Venn (or polyVenn) diagrams are Venn diagrams whose curves are the perimeters of orthogonal polyominoes drawn on the integer lattice. Minimum area polyVenn diagrams are those in which each of the 2n intersection regions, in a diagram of n polyominoes, consists of exactly one unit square. We construct minimum area polyVenn diagrams in bounding rectangles of size 2r×2c whenever rc ≥ 2. Our construction is inductive, and depends on two expansion results. First, a minimum area polyVenn diagram in a 2r×2c rectangle can be expanded to produce another that fits into a 2r+1×2c+1 rectangle. Second, a minimum area polyVenn in a 22×2c rectangle can be expanded to produce another that fits into a 22×2c+3 bounding rectangle. Finally, for even n we construct n-set polyVenn diagrams in bounding rectangles of size (2n/2-1)×(2n/2+1) in which the empty set is not represented as a unit square.

http://jocg.org/index.php/jocg/article/view/91 2012/09/12 - 19:07

Let G be a geometric graph whose vertex set S is a set of n points in ℝd. The stretch factor of two distinct points p and q in S is the ratio of their shortest-path distance in G and their Euclidean distance. We consider the problem of approximating the average of the n choose 2 stretch factors determined by all pairs of points in S. We show that for paths, cycles, and trees, this average can be approximated, within a factor of 1+ε, in O(n polylog(n)) time. For plane graphs in ℝ2, we present a (2+ε)-approximation algorithm with running time O(n5/3polylog(n)), and a (4+ε)-approximation algorithm with running time O(n3/2polylog(n)). Finally, we show that, for any tree in ℝ2, the exact average of the squares of the n choose 2 stretch factors can be computed in O(n11/6) time.

http://jocg.org/index.php/jocg/article/view/87 2012/07/08 - 22:18

We study problems that arise in the context of covering certain geometric objects called seeds (e.g., points or disks) by a set of other geometric objects called cover (e.g., a set of disks or homothetic triangles). We insist that the interiors of the seeds and the cover elements are pairwise disjoint, respectively, but they can touch. We call the contact graph of a cover a cover contact graph (CCG). We are interested in three types of tasks, both in the general case and in the special case of seeds on a line: (a) deciding whether a given seed set has a connected CCG, (b) deciding whether a given graph has a realization as a CCG on a given seed set, and (c) bounding the sizes of certain classes of CCG's. Concerning (a) we give efficient algorithms for the case that seeds are points and show that the problem becomes hard if seeds and covers are disks. Concerning (b) we show that this problem is hard even for point seeds and disk covers (given a fixed correspondence between graph vertices and seeds). Concerning (c) we obtain upper and lower bounds on the number of CCG's for point seeds.

http://jocg.org/index.php/jocg/article/view/66 2012/06/26 - 18:11

Let P be a set of n points in general position in the plane. We study the chromatic number of the intersection graph of the open triangles determined by P. It is known that this chromatic number is at least n3/27+O(n2) and, if P is in convex position, the answer is n3/24+O(n2). We prove that for arbitrary P, the chromatic number is at most n3/19.259+O(n2).

http://jocg.org/index.php/jocg/article/view/78 2012/06/01 - 17:53

We study several set cover problems in low dimensional geometric settings. Specifically, we describe a PTAS for the problem of computing a minimum cover of given points by a set of weighted fat objects. Here, we allow the objects to expand by some prespecified δ-fraction of their diameter.Next, we show that the problem of computing a minimum weight cover of points by weighted halfplanes (without expansion) can be solved exactly in the plane. We also study the problem of covering ℝd by weighted halfspaces, and provide approximation algorithms and hardness results. We also investigate the dual settings of computing minimum weight simplex that covers a given target point.Finally, we provide a near linear time algorithm for the problem of solving a LP minimizing the total weight of violated constraints needed to be removed to make it feasible.

http://jocg.org/index.php/jocg/article/view/77 2012/05/18 - 20:25

A ball graph is an intersection graph of a set of balls with arbitrary radii. Given a real number t>1, we say that a subgraph G' of a graph G is a t-spanner of G, if for every pair of vertices u,v in G, there exists a path in G' of length at most t times the distance between u and v in G. In this paper, we consider the problem of efficiently constructing sparse spanners of ball graphs which supports fast shortest path distance queries. We present the first algorithm for constructing spanners of ball graphs. For a ball graph in Rk, we construct a (1+ε)-spanner for any ε>0 with O(nε-k+1) edges in O(n2ℓ+δε-k logℓ S) time, using an efficient partitioning of space into hypercubes and solving intersection problems. Here ℓ=1-1/(⌊k/2⌋+2), δ is any positive constant, and S is the ratio between the largest and smallest radius. For the special case when the balls all have unit size, we show that the complexity of constructing a (1+ε)-spanner is almost equal to the complexity of constructing a Euclidean minimum spanning tree. The algorithm extends naturally to other disk-like objects, also in higher dimensions. The algorithm uses an efficient subdivision of space to construct a sparse graph having many of the same distance properties as the input ball graph. Additionally, the constructed spanners have a small vertex separator decomposition (hereditary). In dimension k=2, the disk graph spanner has an O(n1/2ε-3/2+ε-3log S) separator. The presence of a small separator is then exploited to obtain very efficient data structures for approximate distance queries. The results on geometric graph separators might be of independent interest. For example, since complete Euclidean graphs are just a special case of (unit) ball graphs, our results also provide a new approach for constructing spanners with small separators in these graphs.

http://jocg.org/index.php/jocg/article/view/31 2012/05/06 - 19:39

In 2008, Bukh, Matoušek, and Nivasch conjectured that for every n-point set S in ℝd and every k, 0 ≤ k ≤ d-1, there exists a k-flat f in ℝd (a centerflat) that lies at depth (k + 1)n/(k + d + 1) - O(1) in S, in the sense that every halfspace that contains f contains at least that many points of S. This claim is true and tight for k = 0 (this is Rado's centerpoint theorem), as well as for k = d-1 (trivial). Bukh et al. showed the existence of a (d - 2)-flat at depth (d - 1)n/(2d - 1) - O(1) (the case k = d - 2). In this paper we concentrate on the case k = 1 (the case of centerlines), in which the conjectured value for the leading constant is 2/(d + 2). We prove that 2/(d + 2) is an upper bound for the leading constant. Specifically, we show that for every fixed d and every n there exists an n-point set in ℝd for which no line in ℝd lies at depth greater than 2n/(d + 2) + o(n). This point set is the stretched grid—a set which has been previously used by Bukh et al. for other related purposes. Hence, in particular, the conjecture is now settled for ℝ3 .

http://jocg.org/index.php/jocg/article/view/80 2012/04/26 - 23:15

A spanner graph on a set of points in Rd provides shortest paths between any pair of points with lengths at most a constant factor of their Euclidean distance. A spanner with a sparse set of edges is thus a good candidate for network backbones, as desired in many practical scenarios such as the transportation network and peer-to-peer network overlays. In this paper we investigate new models and aim to interpret why good spanners ‘emerge’ in reality, when they are clearly built in pieces by agents with their own interests and the construction is not coordinated. We show that the following algorithm of constructing an edge pq, if and only if there is no existing edge pq′ with p′ and q′ at distances no more than (4(1+1/ε))-1·|pq| from p, q respectively, generates a (1+ε)-spanner with a linear number of edges. The algorithm also implies a simple algorithm for constructing linear-size well-separated pair decompositions that may be of interest on their own. This new spanner construction algorithm has applications in the construction of nice network topologies for peer-to-peer systems, when peers join and leave the network and have only limited information about the rest of the network.

http://jocg.org/index.php/jocg/article/view/63 2012/01/03 - 19:09

A Manhattan network for a finite set P of points in the plane is a geometric graph such that its vertex set contains P, its edges are axis-parallel and non-crossing and, for any two points p and q in P, there exists a path in the network connecting p and q whose length equals the l1-distance between p and q.The problem of computing a Manhattan network of minimum total edge length for a given point set P has recently been shown to be NP-hard. In this note, using as the parameter the minimum number h of horizontal straight lines that contain the points in P, we present a fixed-parameter algorithm for this problem running in O*(214h) time and note that, under the exponential time hypothesis for 3-SAT, a run time that is subexponential in h is impossible.

http://jocg.org/index.php/jocg/article/view/43 2011/12/19 - 22:53

Let K be a simplicial complex with vertex set V = v1,…,vn. The complex K is d-representable if there is a collection {C1,…,Cn} of convex sets in Rd such that a subcollection {Ci1,…,Cij} has a nonempty intersection if and only if {vi1,…,vij} is a face of K.In 1967 Wegner proved that every simplicial complex of dimension d is (2d+1)-representable. He also conjectured that his bound is the best possible, i.e., that there are d-dimensional simplicial complexes which are not 2d-representable. However, he was not able to prove his conjecture.We prove that his suggestion was indeed right. Thus we add another piece to the puzzle of intersection patterns of convex sets in Euclidean space.

http://jocg.org/index.php/jocg/article/view/73 2011/11/19 - 23:19

We describe a data structure, a rectangular complex, that can be used represent hyperconvex metric spaces that have the same topology (although not necessarily the same distance function) as subsets of the plane. We show how to use this data structure to construct the tight span of a metric space given as an n×distance matrix, when the tight span is homeomorphic to a subset of the plane, in time O(n2), and to add a single point to a planar tight span in time O(n). As an application of this construction, we show how to test whether a given finite metric space embeds isometrically into the Manhattan plane in time O(n2), and add a single point to the space and re-test whether it has such an embedding in time O(n).

http://jocg.org/index.php/jocg/article/view/61 2011/10/29 - 15:36

Given a set P of points in the plane we are interested in points that are `deep' in the set in the sense that they have two opposite quadrants both containing many points of P. We deal with an extremal version of this problem. A pair (a,b) of numbers is admissible if every point set P contains a point p in P that determines a pair (Q,Qop) of opposite quadrants, such that Q contains at least an a-fraction and Qop contains at least a b-fraction of the points of P. We provide a complete description of the set F of all admissible pairs (a,b). This amounts to identifying three line segments and a point on the boundary of F. In higher dimensions we study the maximum a, such that (a,a) is opposite-orthant admissible. In dimension d we show that 1/(2γ)≤a≤1/γ for γ=22d-12d-1. Finally we deal with a variant of the problem where the opposite pairs of orthants need not be determined by a point in P. Again we are interested in values a, such that all subsets P in Rd admit a pair (O,Oop) of opposite orthants both ontaining at least an a-fraction of the points. The maximum such value is a=1/2d. Generalizations of the problem are also disussed.

http://jocg.org/index.php/jocg/article/view/53 2011/10/19 - 05:48

This paper defines the Arrwwid number of a recursive tiling (or space-filling curve) as the smallest number a such that any ball Q can be covered by a tiles (or curve fragments) with total volume O(volume(Q)). Recursive tilings and space-filling curves with low Arrwwid numbers can be applied to optimize disk, memory or server access patterns when processing sets of points in Rd. This paper presents recursive tilings and space-filling curves with optimal Arrwwid numbers. For d ≥ 3, we see that regular cube tilings and space-filling curves cannot have optimal Arrwwid number, and we see how to construct alternatives with better Arrwwid numbers.

http://jocg.org/index.php/jocg/article/view/68 2011/10/17 - 06:06

We consider the problem of finding a realization of an n-vertex unit disk graph (UDG) expressed in general form, say, as an adjacency matrix. The problem is to construct an embedding of the graph in low-dimensional Euclidean space so that the ratio of the length of the longest edge under the embedding to the length of the shortest non-edge under the embedding is as small as possible; the measure is known as the quality of the realization. Thus, an optimum quality realization has quality between 1/2 and 1. Kuhn et al. gave a O(log3.5 n (loglog n)1/2}) quality realization that requires solving a linear program with exponentially many constraints by using the ellipsoid algorithm.In this article, we give a combinatorial algorithm that achieves an O(log3 n) quality realization of an n-vertex UDG expressed in general form. Thus, not only is our algorithm an improvement, it also bypasses the standard and costly technique of solving a linear program with exponentially many “spreading constraints.” As a side effect of our construction, we get the first constant-factor approximation to the minimum clique partition problem for UDGs expressed in general form. Such a clique partition also represents our key technical contribution. If the embedding is allowed to reside in higher dimensional space, we obtain improved results: a quality-2 embedding in constant dimensional Euclidean space.

http://jocg.org/index.php/jocg/article/view/35 2011/08/15 - 15:35

Constant-work-space algorithms may use only constantly many cells of storage in addition to their input, which is provided as a read-only array. We show how to construct several geometric structures efficiently in the constant-work-space model. Traditional algorithms process the input into a suitable data structure (like a doubly-connected edge list) that allows efficient traversal of the structure at hand. In the constant-work-space setting, however, we cannot afford to do this. Instead, we provide operations that compute the desired features on the fly by accessing the input with no extra space. The whole geometric structure can be obtained by using these operations to enumerate all the features. Of course, we must pay for the space savings by slower running times. While the standard data structure allows us to implement traversal operations in constant time, our schemes typically take linear time to read the input data in each step.We begin with two simple problems: triangulating a planar point set and finding the trapezoidal decomposition of a simple polygon. In both cases adjacent features can be enumerated in linear time per step, resulting in total quadratic running time to output the whole structure. Actually, we show that the former result carries over to the Delaunay triangulation, and hence the Voronoi diagram. This also means that we can compute the largest empty circle of a planar point set in quadratic time and constant work-space. As another application, we demonstrate how to enumerate the features of an Euclidean minimum spanning tree (EMST) in quadratic time per step, so that the whole EMST can be found in cubic time using constant work-space.Finally, we describe how to compute a shortest geodesic path between two points in a simple polygon. Although the shortest path problem in general graphs is NL-complete (Jakoby and Tantau 2003), this constrained problem can be solved in quadratic time using only constant work-space.

http://jocg.org/index.php/jocg/article/view/30 2011/07/04 - 09:44