Vaguery + computational-geometry   366

 « earlier
[1807.09977] Colored range closest-pair problem under general distance functions
The range closest-pair (RCP) problem is the range-search version of the classical closest-pair problem, which aims to store a given dataset of points in some data structure such that when a query range X is specified, the closest pair of points contained in X can be reported efficiently. A natural generalization of the RCP problem is the {colored range closest-pair} (CRCP) problem in which the given data points are colored and the goal is to find the closest {bichromatic} pair contained in the query range. All the previous work on the RCP problem was restricted to the uncolored version and the Euclidean distance function. In this paper, we make the first progress on the CRCP problem. We investigate the problem under a general distance function induced by a monotone norm; in particular, this covers all the Lp-metrics for p>0 and the L∞-metric. We design efficient (1+ε)-approximate CRCP data structures for orthogonal queries in ℝ2, where ε>0 is a pre-specified parameter. The highlights are two data structures for answering rectangle queries, one of which uses O(ε−1nlog4n) space and O(log4n+ε−1log3n+ε−2logn) query time while the other uses O(ε−1nlog3n) space and O(log5n+ε−1log4n+ε−2log2n) query time. In addition, we also apply our techniques to the CRCP problem in higher dimensions, obtaining efficient data structures for slab, 2-box, and 3D dominance queries. Before this paper, almost all the existing results for the RCP problem were achieved in ℝ2.
computational-complexity  computational-geometry  algorithms  horse-races  to-write-about  nudge-targets  consider:looking-to-see  consider:relaxations  consider:representation
7 days ago by Vaguery
[1312.1001] Optimal detection of intersections between convex polyhedra
For a polyhedron P in ℝd, denote by |P| its combinatorial complexity, i.e., the number of faces of all dimensions of the polyhedra. In this paper, we revisit the classic problem of preprocessing polyhedra independently so that given two preprocessed polyhedra P and Q in ℝd, each translated and rotated, their intersection can be tested rapidly.
For d=3 we show how to perform such a test in O(log|P|+log|Q|) time after linear preprocessing time and space. This running time is the best possible and improves upon the last best known query time of O(log|P|log|Q|) by Dobkin and Kirkpatrick (1990).
We then generalize our method to any constant dimension d, achieving the same optimal O(log|P|+log|Q|) query time using a representation of size O(|P|⌊d/2⌋+ε) for any ε>0 arbitrarily small. This answers an even older question posed by Dobkin and Kirkpatrick 30 years ago.
In addition, we provide an alternative O(log|P|+log|Q|) algorithm to test the intersection of two convex polygons P and Q in the plane.
computational-complexity  computational-geometry  algorithms  rather-interesting  consider:performance-measures  to-write-about  nudge-targets
7 days ago by Vaguery
[1809.07481] $L_1$ Shortest Path Queries in Simple Polygons
Let P be a simple polygon of n vertices. We consider two-point L1 shortest path queries in P. We build a data structure of O(n) size in O(n) time such that given any two query points s and t, the length of an L1 shortest path from s to t in P can be computed in O(logn) time, or in O(1) time if both s and t are vertices of P, and an actual shortest path can be output in additional linear time in the number of edges of the path. To achieve the result, we propose a mountain decomposition of simple polygons, which may be interesting in its own right. Most importantly, our approach is much simpler than the previous work on this problem.
computational-geometry  planning  algorithms  computational-complexity  representation  to-write-about  consider:feature-discovery
17 days ago by Vaguery
[1603.02853] A Time-Space Trade-off for Computing the k-Visibility Region of a Point in a Polygon
Let P be a simple polygon with n vertices, and let q∈P be a point in P. Let k∈{0,…,n−1}. A point p∈P is k-visible from q if and only if the line segment pq crosses the boundary of P at most k times. The k-visibility region of q in P is the set of all points that are k-visible from q. We study the problem of computing the k-visibility region in the limited workspace model, where the input resides in a random-access read-only memory of O(n) words, each with Ω(logn) bits. The algorithm can read and write O(s) additional words of workspace, where s∈ℕ is a parameter of the model. The output is written to a write-only stream.
Given a simple polygon P with n vertices and a point q∈P, we present an algorithm that reports the k-visibility region of q in P in O(cn/s+clogs+min{⌈k/s⌉n,nloglogsn}) expected time using O(s) words of workspace. Here, c∈{1,…,n} is the number of critical vertices of P for q where the k-visibility region of q may change. We generalize this result for polygons with holes and for sets of non-crossing line segments.
computational-geometry  plane-geometry  algorithms  polygon-visibility  computational-complexity  nudge-targets
17 days ago by Vaguery
[1706.08105] Compatible 4-Holes in Point Sets
Counting interior-disjoint empty convex polygons in a point set is a typical Erdős-Szekeres-type problem. We study this problem for 4-gons. Let P be a set of n points in the plane and in general position. A subset Q of P, with four points, is called a 4-hole in P if Q is in convex position and its convex hull does not contain any point of P in its interior. Two 4-holes in P are compatible if their interiors are disjoint. We show that P contains at least ⌊5n/11⌋−1 pairwise compatible 4-holes. This improves the lower bound of 2⌊(n−2)/5⌋ which is implied by a result of Sakai and Urrutia (2007).
computational-geometry  plane-geometry  limits  proof  nudge-targets  to-write-about  to-simulate
21 days ago by Vaguery
[1802.06223] The Geodesic Farthest-point Voronoi Diagram in a Simple Polygon
Given a set of point sites in a simple polygon, the geodesic farthest-point Voronoi diagram partitions the polygon into cells, at most one cell per site, such that every point in a cell has the same farthest site with respect to the geodesic metric. We present an O(nloglogn+mlogm)- time algorithm to compute the geodesic farthest-point Voronoi diagram of m point sites in a simple n-gon. This improves the previously best known algorithm by Aronov et al. [Discrete Comput. Geom. 9(3):217-255, 1993]. In the case that all point sites are on the boundary of the simple polygon, we can compute the geodesic farthest-point Voronoi diagram in O((n+m)loglogn) time.
computational-geometry  algorithms  computational-complexity  to-understand  to-simulate  nudge-targets  consider:looking-to-see
22 days ago by Vaguery
[1703.09533] Routing in Polygonal Domains
We consider the problem of routing a data packet through the visibility graph of a polygonal domain P with n vertices and h holes. We may preprocess P to obtain a label and a routing table for each vertex of P. Then, we must be able to route a data packet between any two vertices p and q of P, where each step must use only the label of the target node q and the routing table of the current node.
For any fixed ε>0, we present a routing scheme that always achieves a routing path whose length exceeds the shortest path by a factor of at most 1+ε. The labels have O(logn) bits, and the routing tables are of size O((ε−1+h)logn). The preprocessing time is O(n2logn). It can be improved to O(n2) for simple polygons.
planning  computational-geometry  operations-research  algorithms  computational-complexity  layered-problems  to-write-about
22 days ago by Vaguery
Largest and Smallest Convex Hulls for Imprecise Points | SpringerLink
Assume that a set of imprecise points is given, where each point is specified by a region in which the point may lie. We study the problem of computing the smallest and largest possible convex hulls, measured by length and by area. Generally we assume the imprecision region to be a square, but we discuss the case where it is a segment or circle as well. We give polynomial time algorithms for several variants of this problem, ranging in running time from O(nlog n) to O(n 13), and prove NP-hardness for some other variants.
computational-geometry  plane-geometry  optimization  uncertainty  imprecision  rather-interesting  to-write-about  nudge-targets
27 days ago by Vaguery
[1712.08911] Largest and Smallest Area Triangles on Imprecise Points
Assume we are given a set of parallel line segments in the plane, and we wish to place a point on each line segment such that the resulting point set maximizes or minimizes the area of the largest or smallest triangle in the set. We analyze the complexity of the four resulting computational problems, and we show that three of them admit polynomial-time algorithms, while the fourth is NP-hard. Specifically, we show that maximizing the largest triangle can be done in O(n2) time (or in O(nlogn) time for unit segments); minimizing the largest triangle can be done in O(n2logn) time; maximizing the smallest triangle is NP-hard; but minimizing the smallest triangle can be done in O(n2) time. We also discuss to what extent our results can be generalized to polygons with k>3 sides.
computational-geometry  rather-interesting  approximation  plane-geometry  optimization  to-write-about  nudge-targets  consider:looking-to-see
27 days ago by Vaguery
[1712.05081] Linear time Minimum Area All-flush Triangles Circumscribing a Convex Polygon
We study the problem of computing the minimum area triangle that circumscribes a given n-sided convex polygon touching edge-to-edge. In other words, we compute the minimum area triangle that is the intersection of 3 half-planes out of n half-planes defined by a given convex polygon. Building on the Rotate-and-Kill technique {arXiv:1707.04071}, we propose an algorithm that solves the problem in O(n) time, improving the best-known O(nlogn) time algorithms given in [A. Aggarwal et. al. DCG94; B. Schieber. SODA95}. Our algorithm computes all the locally minimal area circumscribing triangles touching edge-to-edge.
computational-geometry  algorithms  plane-geometry  rather-interesting  to-write-about  nudge-targets  consider:looking-to-see
27 days ago by Vaguery
[1705.11035] Maximum-Area Triangle in a Convex Polygon, Revisited
We revisit the following problem: Given a convex polygon P, find the largest-area inscribed triangle. We show by example that the linear-time algorithm presented in 1979 by Dobkin and Snyder for solving this problem fails. We then proceed to show that with a small adaptation, their approach does lead to a quadratic-time algorithm. We also present a more involved O(nlogn) time divide-and-conquer algorithm. Also we show by example that the algorithm presented in 1979 by Dobkin and Snyder for finding the largest-area k-gon that is inscribed in a convex polygon fails to find the optimal solution for k=4. Finally, we discuss the implications of our discoveries on the literature.
computational-geometry  optimization  plane-geometry  rather-interesting  to-write-about  oopsie  nudge-targets  consider:looking-to-see
27 days ago by Vaguery
[1707.04071] Maximal Area Triangles in a Convex Polygon
The widely known linear time algorithm for computing the maximum area triangle in a convex polygon was found incorrect recently by Keikha et. al.(arXiv:1705.11035). We present an alternative algorithm in this paper. Comparing to the only previously known correct solution, ours is much simpler and more efficient. More importantly, our new approach is powerful in solving related problems.
computational-geometry  algorithms  plane-geometry  rather-interesting  nudge-targets  consider:looking-to-see  to-write-about
27 days ago by Vaguery
[1809.06451] A new lower bound on Hadwiger-Debrunner numbers in the plane
A family of sets F is said to satisfy the (p,q) property if among any p sets in F, some q have a non-empty intersection. Hadwiger and Debrunner (1957) conjectured that for any p≥q≥d+1 there exists c=cd(p,q), such that any family of compact convex sets in ℝd that satisfies the (p,q) property, can be pierced by at most c points. In a celebrated result from 1992, Alon and Kleitman proved the conjecture. However, obtaining sharp bounds on cd(p,q), called the Hadwiger-Debrunner numbers', is still a major open problem in discrete and computational geometry. The best currently known lower bound on the Hadwiger-Debrunner numbers in the plane is c2(p,q)=Ω(pqlog(pq)) while the best known upper bound is O(p(1.5+δ)(1+1q−2)).
In this paper we improve the lower bound significantly by showing that c2(p,q)≥p1+Ω(1/q). Furthermore, the bound is obtained by a family of lines, and is tight for all families that have a bounded VC-dimension. Unlike previous bounds on the Hadwiger-Debrunner numbers which mainly used the weak epsilon-net theorem, our bound stems from a surprising connection of the (p,q) problem to an old problem of Erdős on points in general position in the plane. We use a novel construction for the Erdős' problem, obtained recently by Balogh and Solymosi using the hypergraph container method, to get the lower bound on c2(p,3). We then generalize the bound to c2(p,q) for any q≥3.
computational-geometry  plane-geometry  to-understand  graph-theory  proof  nudge-targets  consider:looking-to-see  also:a-fucking-drawing-or-two-might-be-nice-people
27 days ago by Vaguery
[1512.04349] Clustering time series under the Fr'echet distance
e Fréchet distance is a popular distance measure for curves. We study the problem of clustering time series under the Fréchet distance. In particular, we give (1+ε)-approximation algorithms for variations of the following problem with parameters k and ℓ. Given n univariate time series P, each of complexity at most m, we find k time series, not necessarily from P, which we call \emph{cluster centers} and which each have complexity at most ℓ, such that (a) the maximum distance of an element of P to its nearest cluster center or (b) the sum of these distances is minimized. Our algorithms have running time near-linear in the input size for constant ε, k and ℓ. To the best of our knowledge, our algorithms are the first clustering algorithms for the Fréchet distance which achieve an approximation factor of (1+ε) or better.
Keywords: time series, longitudinal data, functional data, clustering, Fréchet distance, dynamic time warping, approximation algorithms.
computational-geometry  algorithms  metrics  clustering  to-understand  time-series
6 weeks ago by Vaguery
Fréchet distance - Wikipedia
In mathematics, the Fréchet distance is a measure of similarity between curves that takes into account the location and ordering of the points along the curves. It is named after Maurice Fréchet.
measurement  metrics  data-analysis  feature-construction  distance  computational-geometry  to-consider  ReQ
6 weeks ago by Vaguery
We define a plane curve to be threadable if it can rigidly pass through a point-hole in a line L without otherwise touching L. Threadable curves are in a sense generalizations of monotone curves. We have two main results. The first is a linear-time algorithm for deciding whether a polygonal curve is threadable---O(n) for a curve of n vertices---and if threadable, finding a sequence of rigid motions to thread it through a hole. We also sketch an argument that shows that the threadability of algebraic curves can be decided in time polynomial in the degree of the curve. The second main result is an O(n polylog n)-time algorithm for deciding whether a 3D polygonal curve can thread through hole in a plane in R^3, and if so, providing a description of the rigid motions that achieve the threading.
computational-geometry  geometry  rather-interesting  definition  nudge-targets  consider:feature-discovery  to-write-about  consider:algorithms
october 2018 by Vaguery
The mathematician Leo Moser posed in 1966 the following curious mathematical problem: what is the shape of largest area in the plane that can be moved around a right-angled corner in a two-dimensional hallway of width 1? This question became known as the moving sofa problem, and is still unsolved fifty years after it was first asked.
mathematical-recreations  computational-geometry  engineering-design  constraint-satisfaction  rather-interesting  nudge-targets  to-write-about
april 2018 by Vaguery
[1801.07008] INKA: An Ink-based Model of Graph Visualization
Common quality metrics of graph drawing have been about the readability criteria, such as small number of edge crossings, small drawing area and small total edge length. Bold graph drawing considers more realistic drawings consisting of vertices as disks of some radius and edges as rectangles of some width. However, the relationship that links these readability criteria with the rendering criteria in node-link diagrams has still not been well-established.
This paper introduces a model, so-called INKA (Ink-Active), that encapsulates mathematically the relationship between all common drawing factors. Consequently, we investigate our INKA model on several common drawing algorithms and real-world graphs.
computational-geometry  graph-layout  LaTeX  algorithms  maybe-try-multiobjective  to-write-about
march 2018 by Vaguery
[1802.06415] Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality
We consider practical methods for the problem of finding a minimum-weight triangulation (MWT) of a planar point set, a classic problem of computational geometry with many applications. While Mulzer and Rote proved in 2006 that computing an MWT is NP-hard, Beirouti and Snoeyink showed in 1998 that computing provably optimal solutions for MWT instances of up to 80,000 uniformly distributed points is possible, making use of clever heuristics that are based on geometric insights. We show that these techniques can be refined and extended to instances of much bigger size and different type, based on an array of modifications and parallelizations in combination with more efficient geometric encodings and data structures. As a result, we are able to solve MWT instances with up to 30,000,000 uniformly distributed points in less than 4 minutes to provable optimality. Moreover, we can compute optimal solutions for a vast array of other benchmark instances that are not uniformly distributed, including normally distributed instances (up to 30,000,000 points), all point sets in the TSPLIB (up to 85,900 points), and VLSI instances with up to 744,710 points. This demonstrates that from a practical point of view, MWT instances can be handled quite well, despite their theoretical difficulty.
computational-geometry  algorithms  plane-geometry  optimization  to-write-about  nudge-targets  consider:representation
march 2018 by Vaguery
[1606.06532] Eulerian triangulations: two-point function and hull perimeter statistics
We present a new derivation of the distance-dependent two-point function for planar Eulerian triangulations and give expressions for more refined generating functions where we also control hull perimeters. These results are obtained in the framework of a new recursion relation for slice generating functions and extend similar results obtained recently for triangulations and quadrangulations. A number of explicit formulas are given for the statistics of hull perimeters in infinitely large random planar Eulerian triangulations.
computational-geometry  combinatorics  to-understand  triangulation
february 2018 by Vaguery
fully open-access journal with explicit integration into distributed scholarly archives and libraries
february 2018 by Vaguery
[1712.02657] Generalised primal-dual grids for unstructured co-volume schemes
The generation of high-quality staggered unstructured grids for computational simulation is considered; leading to the development of a new optimisation-based strategy for the construction of weighted Regular-Power' tessellations appropriate for co-volume type numerical techniques. This new framework aims to extend the conventional Delaunay-Voronoi primal-dual structure; seeking to assemble generalised orthogonal tessellations with enhanced geometric quality. The construction of these grids is motivated by the desire to improve the performance and accuracy of numerical methods based on unstructured co-volume type schemes, including various staggered grid techniques for the simulation of fluid dynamics and hyperbolic transport. In this study, a hybrid optimisation strategy is proposed; seeking to optimise the geometry, topology and weights associated with general, two-dimensional Regular-Power tessellations using a combination of gradient-ascent and energy-based techniques. The performance of the new method is tested experimentally, with a range of complex, multi-resolution primal-dual grids generated for various coastal and regional ocean modelling applications.
finite-elements-methods  computational-geometry  algorithms  performance-measure  rather-interesting  to-write-about  to-simulate
january 2018 by Vaguery
[1712.05390] Partisan gerrymandering with geographically compact districts
Bizarrely shaped voting districts are frequently lambasted as likely instances of gerrymandering. In order to systematically identify such instances, researchers have devised several tests for so-called geographic compactness (i.e., shape niceness). We demonstrate that under certain conditions, a party can gerrymander a competitive state into geographically compact districts to win an average of over 70% of the districts. Our results suggest that geometric features alone may fail to adequately combat partisan gerrymandering.
computational-geometry  politics  multiobjective-optimization  rather-interesting  to-write-about  consider:looking-to-see  nudge-targets  consider:stochastic-versions
december 2017 by Vaguery
[1708.08691] Extremal solutions to some art gallery and terminal-pairability problems
The chosen tool of this thesis is an extremal type approach. The lesson drawn by the theorems proved in the thesis is that surprisingly small compromise is necessary on the efficacy of the solutions to make the approach work. The problems studied have several connections to other subjects and practical applications.
The first part of the thesis is concerned with orthogonal art galleries. A sharp extremal bound is proved on partitioning orthogonal polygons into at most 8-vertex polygons using established techniques in the field of art gallery problems. This fills in the gap between already known results for partitioning into at most 6- and 10-vertex orthogonal polygons.
Next, these techniques are further developed to prove a new type of extremal art gallery result. The novelty provided by this approach is that it establishes a connection between mobile and stationary guards. This theorem has strong computational consequences, in fact, it provides the basis for an 83-approximation algorithm for guarding orthogonal polygons with rectangular vision.
In the second part, the graph theoretical concept of terminal-pairability is studied in complete and complete grid graphs. Once again, the extremal approach is conductive to discovering efficient methods to solve the problem.
In the case of a complete base graph, the new demonstrated lower bound on the maximum degree of realizable demand graphs is 4 times higher than previous best results. The techniques developed are then used to solve the classical extremal edge number problem for the terminal-pairability problem in complete base graphs.
The complete grid base graph lies on the other end of the spectrum in terms density amongst path-pairable graphs. It is shown that complete grid graphs are relatively efficient in routing edge-disjoint paths.
computational-geometry  combinatorics  plane-geometry  extreme-values  rather-interesting  to-write-about  nudge-targets  consider:approximation  consider:looking-to-see
november 2017 by Vaguery
[1711.02450] Shape Representation by Zippable Ribbons
Shape fabrication from developable parts is the basis for arts such as papercraft and needlework, as well as modern architecture and CAD in general, and it has inspired much research. We observe that the assembly of complex 3D shapes created by existing methods often requires first fabricating many small flat parts and then carefully following instructions to assemble them together. Despite its significance, this error prone and tedious process is generally neglected in the discussion. We propose an approach for shape representation through a single developable part that attaches to itself and requires no assembly instructions. Our inspiration comes from the so-called zipit bags, which are made of a single, long ribbon with a zipper around its boundary. In order to "assemble" the bag, one simply needs to zip up the ribbon. Our method operates in the same fashion, but it can be used to approximate any shape. Given a 3D model, our algorithm produces plans for a single 2D shape that can be laser cut in few parts from flat fabric or paper. We can then attach a zipper along the boundary for quick assembly and disassembly, or apply more traditional approaches, such as gluing and stitching. We show physical and virtual results that demonstrate the capabilities of our method and the ease with which shapes can be assembled.
november 2017 by Vaguery
[1308.5550] Fitting Voronoi Diagrams to Planar Tesselations
Given a tesselation of the plane, defined by a planar straight-line graph G, we want to find a minimal set S of points in the plane, such that the Voronoi diagram associated with S "fits" \ G. This is the Generalized Inverse Voronoi Problem (GIVP), defined in \cite{Trin07} and rediscovered recently in \cite{Baner12}. Here we give an algorithm that solves this problem with a number of points that is linear in the size of G, assuming that the smallest angle in G is constant.
inverse-problems  computational-geometry  rather-interesting  nudge-targets  consider:looking-to-see  to-write-about
november 2017 by Vaguery
[1705.04715] A catalogue of 4-regular and (2,4)-regular matchstick graphs
The first part (page 1 - 6) of this article presents the currently known examples of 4-regular matchstick graphs with 63 - 70 vertices. The second part (page 7 - 13) presents the currently known examples of (2,4)-regular matchstick graphs with less than 42 vertices which contain only two vertices of degree 2.
stamp-collecting  combinatorics  graph-theory  computational-geometry  rather-interesting  to-w  anomaly-detection  consider:looking-to-see
november 2017 by Vaguery
[1205.2425] Flip Distance Between Two Triangulations of a Point-Set is NP-complete
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.
computational-complexity  computational-geometry  algorithms  planning  optimization  rather-interesting  plane-geometry  nudge-targets  consider:looking-to-see
november 2017 by Vaguery
[1601.01298] Visibility Graphs, Dismantlability, and the Cops and Robbers Game
We study versions of cop and robber pursuit-evasion games on the visibility graphs of polygons, and inside polygons with straight and curved sides. Each player has full information about the other player's location, players take turns, and the robber is captured when the cop arrives at the same point as the robber. In visibility graphs we show the cop can always win because visibility graphs are dismantlable, which is interesting as one of the few results relating visibility graphs to other known graph classes. We extend this to show that the cop wins games in which players move along straight line segments inside any polygon and, more generally, inside any simply connected planar region with a reasonable boundary. Essentially, our problem is a type of pursuit-evasion using the link metric rather than the Euclidean metric, and our result provides an interesting class of infinite cop-win graphs.
computational-geometry  game-theory  rather-interesting  to-write-about  nudge-targets  consider:representation  consider:splinegons
november 2017 by Vaguery
[1710.02741] A Proof of the Orbit Conjecture for Flipping Edge-Labelled Triangulations
Given a triangulation of a point set in the plane, a \emph{flip} deletes an edge e whose removal leaves a convex quadrilateral, and replaces e by the opposite diagonal of the quadrilateral. It is well known that any triangulation of a point set can be reconfigured to any other triangulation by some sequence of flips. We explore this question in the setting where each edge of a triangulation has a label, and a flip transfers the label of the removed edge to the new edge.
It is not true that every labelled triangulation of a point set can be reconfigured to every other labelled triangulation via a sequence of flips. We characterize when this is possible by proving the \emph{Orbit Conjecture} of Bose, Lubiw, Pathak and Verdonschot which states that \emph{all} labels can be simultaneously mapped to their destination if and only if \emph{each} label individually can be mapped to its destination.
Furthermore, we give a polynomial-time algorithm to find a sequence of flips to reconfigure one labelled triangulation to another, if such a sequence exists, and we prove an upper bound of O(n7) on the length of the flip sequence.
Our proof uses the topological result that the sets of pairwise non-crossing edges on a planar point set form a simplicial complex that is homeomorphic to a high-dimensional ball (this follows from a result of Orden and Santos; we give a different proof based on a shelling argument). The dual cell complex of this simplicial ball, called the \emph{flip complex}, has the usual flip graph as its 1-skeleton. We use properties of the 2-skeleton of the flip complex to prove the Orbit Conjecture.
computational-geometry  proof  rather-interesting  to-write-about  to-simulate  plane-geometry
november 2017 by Vaguery
[1405.2378] Covering Folded Shapes
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→R2). 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.
computational-geometry  to-write  paper-folding  rather-interesting  nudge-targets  consider:algorithms  consider:feature-discovery
november 2017 by Vaguery
[1411.6371] Folding a Paper Strip to Minimize Thickness
In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a "flat folding" is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where "thicker" creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.
paper-folding  computational-geometry  optimization  rather-interesting  to-write-about  to-simulate  nudge-targets  consider:feature-discovery
november 2017 by Vaguery
[1605.06848] Nonnegative Matrix Factorization Requires Irrationality
Nonnegative matrix factorization (NMF) is the problem of decomposing a given nonnegative n×m matrix M into a product of a nonnegative n×d matrix W and a nonnegative d×m matrix H. A longstanding open question, posed by Cohen and Rothblum in 1993, is whether a rational matrix M always has an NMF of minimal inner dimension d whose factors W and H are also rational. We answer this question negatively, by exhibiting a matrix for which W and H require irrational entries.
matrices  computational-geometry  rather-interesting  to-write-about  to-understand  representation  proof  consider:classification
november 2017 by Vaguery
[1707.00219] Angle-monotone Paths in Non-obtuse Triangulations
We reprove a result of Dehkordi, Frati, and Gudmundsson: every two vertices in a non-obtuse triangulation of a point set are connected by an angle-monotone path--an xy-monotone path in an appropriately rotated coordinate system. We show that this result cannot be extended to angle-monotone spanning trees, but can be extended to boundary-rooted spanning forests. The latter leads to a conjectural edge-unfolding of sufficiently shallow polyhedral convex caps.
computational-geometry  plane-geometry  rather-interesting  proof  nudge-targets  consider:looking-to-see  consider:algorithms
november 2017 by Vaguery
[1206.0303] A History of Flips in Combinatorial Triangulations
Given two combinatorial triangulations, how many edge flips are necessary and sufficient to convert one into the other? This question has occupied researchers for over 75 years. We provide a comprehensive survey, including full proofs, of the various attempts to answer it.
computational-geometry  plane-geometry  rather-interesting  algorithms  open-problems  nudge-targets  to-write-about  to-simulate
november 2017 by Vaguery
[1001.0695] The Geodesic Diameter of Polygonal Domains
This paper studies the geodesic diameter of polygonal domains having h holes and n corners. For simple polygons (i.e., h = 0), the geodesic diameter is determined by a pair of corners of a given polygon and can be computed in linear time, as known by Hershberger and Suri. For general polygonal domains with h >= 1, however, no algorithm for computing the geodesic diameter was known prior to this paper. In this paper, we present the first algorithms that compute the geodesic diameter of a given polygonal domain in worst-case time O(n^7.73) or O(n^7 (log n + h)). The main difficulty unlike the simple polygon case relies on the following observation revealed in this paper: two interior points can determine the geodesic diameter and in that case there exist at least five distinct shortest paths between the two.
computational-complexity  computational-geometry  distance  algorithms  rather-interesting  plane-geometry  optimization  nudge-targets  consider:looking-to-see
november 2017 by Vaguery
[1501.00561] A linear-time algorithm for the geodesic center of a simple polygon
Given two points in a simple polygon P of n vertices, its geodesic distance is the length of the shortest path that connects them among all paths that stay within P. The geodesic center of P is the unique point in P that minimizes the largest geodesic distance to all other points of P. In 1989, Pollack, Sharir and Rote [Disc. \& Comput. Geom. 89] showed an O(nlogn)-time algorithm that computes the geodesic center of P. Since then, a longstanding question has been whether this running time can be improved (explicitly posed by Mitchell [Handbook of Computational Geometry, 2000]). In this paper we affirmatively answer this question and present a linear time algorithm to solve this problem.
computational-complexity  computational-geometry  optimization  rather-interesting  algorithms  distance  nudge-targets  consider:rediscovery  consider:feature-discovery
november 2017 by Vaguery
[1604.08797] Ortho-polygon Visibility Representations of Embedded Graphs
An ortho-polygon visibility representation of an n-vertex embedded graph G (OPVR of G) is an embedding-preserving drawing of G that maps every vertex to a distinct orthogonal polygon and each edge to a vertical or horizontal visibility between its end-vertices. The vertex complexity of an OPVR of G is the minimum k such that every polygon has at most k reflex corners. We present polynomial time algorithms that test whether G has an OPVR and, if so, compute one of minimum vertex complexity. We argue that the existence and the vertex complexity of an OPVR of G are related to its number of crossings per edge and to its connectivity. More precisely, we prove that if G has at most one crossing per edge (i.e., G is a 1-plane graph), an OPVR of G always exists while this may not be the case if two crossings per edge are allowed. Also, if G is a 3-connected 1-plane graph, we can compute an OPVR of G whose vertex complexity is bounded by a constant in O(n) time. However, if G is a 2-connected 1-plane graph, the vertex complexity of any OPVR of G may be Ω(n). In contrast, we describe a family of 2-connected 1-plane graphs for which an embedding that guarantees constant vertex complexity can be computed in O(n) time. Finally, we present the results of an experimental study on the vertex complexity of ortho-polygon visibility representations of 1-plane graphs.
graph-layout  computational-geometry  optimization  rather-interesting  to-write-about  nudge-targets  consider:representation  consider:feature-discovery  algorithms  computational-complexity
november 2017 by Vaguery
[0904.2115] Colorful Strips
Given a planar point set and an integer k, we wish to color the points with k colors so that any axis-aligned strip containing enough points contains all colors. The goal is to bound the necessary size of such a strip, as a function of k. We show that if the strip size is at least 2k−1, such a coloring can always be found. We prove that the size of the strip is also bounded in any fixed number of dimensions. In contrast to the planar case, we show that deciding whether a 3D point set can be 2-colored so that any strip containing at least three points contains both colors is NP-complete.
We also consider the problem of coloring a given set of axis-aligned strips, so that any sufficiently covered point in the plane is covered by k colors. We show that in d dimensions the required coverage is at most d(k−1)+1.
Lower bounds are given for the two problems. This complements recent impossibility results on decomposition of strip coverings with arbitrary orientations. Finally, we study a variant where strips are replaced by wedges.
computational-geometry  proof  rather-interesting  to-write-about  hypergraphs  coloring  consider:algorithms
november 2017 by Vaguery
[0705.4085] The Distance Geometry of Music
We demonstrate relationships between the classic Euclidean algorithm and many other fields of study, particularly in the context of music and distance geometry. Specifically, we show how the structure of the Euclidean algorithm defines a family of rhythms which encompass over forty timelines (\emph{ostinatos}) from traditional world music. We prove that these \emph{Euclidean rhythms} have the mathematical property that their onset patterns are distributed as evenly as possible: they maximize the sum of the Euclidean distances between all pairs of onsets, viewing onsets as points on a circle. Indeed, Euclidean rhythms are the unique rhythms that maximize this notion of \emph{evenness}. We also show that essentially all Euclidean rhythms are \emph{deep}: each distinct distance between onsets occurs with a unique multiplicity, and these multiplicies form an interval 1,2,...,k−1. Finally, we characterize all deep rhythms, showing that they form a subclass of generated rhythms, which in turn proves a useful property called shelling. All of our results for musical rhythms apply equally well to musical scales. In addition, many of the problems we explore are interesting in their own right as distance geometry problems on the circle; some of the same problems were explored by Erd\H{o}s in the plane.
music  mathematical-recreations  computational-geometry  rather-interesting  to-write-about  rhythm
october 2017 by Vaguery
[1503.04871] Strong Matching of Points with Geometric Shapes
Let P be a set of n points in general position in the plane. Given a convex geometric shape S, a geometric graph GS(P) on P is defined to have an edge between two points if and only if there exists an empty homothet of S having the two points on its boundary. A matching in GS(P) is said to be strong, if the homothests of S representing the edges of the matching, are pairwise disjoint, i.e., do not share any point in the plane. We consider the problem of computing a strong matching in GS(P), where S is a diametral-disk, an equilateral-triangle, or a square. We present an algorithm which computes a strong matching in GS(P); if S is a diametral-disk, then it computes a strong matching of size at least ⌈n−117⌉, and if S is an equilateral-triangle, then it computes a strong matching of size at least ⌈n−19⌉. If S can be a downward or an upward equilateral-triangle, we compute a strong matching of size at least ⌈n−14⌉ in GS(P). When S is an axis-aligned square we compute a strong matching of size ⌈n−14⌉ in GS(P), which improves the previous lower bound of ⌈n5⌉.
computational-geometry  plane-geometry  rather-interesting  graph-theory  to-write-about  consider:inverse-problem  consider:find-shape-for-points
october 2017 by Vaguery
[1211.2734] Fixed-Orientation Equilateral Triangle Matching of Point Sets
Given a point set P and a class  of geometric objects, G(P) is a geometric graph with vertex set P such that any two vertices p and q are adjacent if and only if there is some C∈ containing both p and q but no other points from P. We study G▽(P) graphs where ▽ is the class of downward equilateral triangles (ie. equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half-Θ6 graphs and TD-Delaunay graphs.
The main result in our paper is that for point sets P in general position, G▽(P) always contains a matching of size at least ⌈n−23⌉ and this bound cannot be improved above ⌈n−13⌉.
We also give some structural properties of $G_{\davidsstar}(P)$ graphs, where $\davidsstar$ is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of $G_{\davidsstar}(P)$ is simply a path. Through the equivalence of $G_{\davidsstar}(P)$ graphs with Θ6 graphs, we also derive that any Θ6 graph can have at most 5n−11 edges, for point sets in general position.
october 2017 by Vaguery
[0705.0635] Moving Walkways, Escalators, and Elevators
We study a simple geometric model of transportation facility that consists of two points between which the travel speed is high. This elementary definition can model shuttle services, tunnels, bridges, teleportation devices, escalators or moving walkways. The travel time between a pair of points is defined as a time distance, in such a way that a customer uses the transportation facility only if it is helpful.
We give algorithms for finding the optimal location of such a transportation facility, where optimality is defined with respect to the maximum travel time between two points in a given set.
operations-research  rather-interesting  computational-geometry  performance-measure  nudge-targets  mathematical-recreations  to-write-about  consider:looking-to-see
october 2017 by Vaguery
[1604.07134] New minimal (4,n)-regular matchstick graphs
A matchstick graph is a graph drawn with straight edges in the plane such that the edges have unit length, and non-adjacent edges do not intersect. We call a matchstick graph (m,n)-regular if every vertex has only degree m or n. In this article the authors present the latest known (4,n)-regular matchstick graphs for 4≤n≤11 with a minimum number of vertices.
computational-geometry  graph-theory  rather-interesting  nudge-targets  consider:looking-to-see  constraint-satisfaction  plane-geometry
october 2017 by Vaguery
[1705.00293] On the existence of 4-regular matchstick graphs
A matchstick graph is a planar unit-distance graph. That is a graph drawn with straight edges in the plane such that the edges have unit length, and non-adjacent edges do not intersect. We call a matchstick graph 4-regular if every vertex has only degree 4. Examples of 4-regular matchstick graphs with less than 63 vertices are only known for 52, 54, 57 and 60 vertices. It is shown that for all number of vertices ≥63 at least one example of a 4-regular matchstick graph exists.
graph-theory  combinatorics  computational-geometry  rather-interesting  constraint-satisfaction  nudge-targets  consider:looking-to-see
october 2017 by Vaguery
[1609.06972] Minimal completely asymmetric (4,n)-regular matchstick graphs
A matchstick graph is a graph drawn with straight edges in the plane such that the edges have unit length, and non-adjacent edges do not intersect. We call a matchstick graph $(m,n)$-regular if every vertex has only degree $m$ or $n$. In this article we present the latest known $(4,n)$-regular matchstick graphs for $4\leq n\leq11$ with a minimum number of vertices and a completely asymmetric structure. We call a matchstick graph completely asymmetric, if the following conditions are complied. 1) The graph is rigid. 2) The graph has no point, rotational or mirror symmetry. 3) The graph has an asymmetric outer shape. 4) The graph can not be decomposed into rigid subgraphs and rearrange to a similar graph which contradicts to any of the other conditions.
computational-geometry  graph-theory  rather-interesting  purdy-pitchers  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery
october 2017 by Vaguery
[1512.02960] Ensembles of Cycles Programmed in GiNaC
This library manipulates ensembles of cycles (quadrics), which are interrelated through certain geometric relations (to be orthogonal, to be tangent, etc.). The code operates with numeric and symbolic data of cycles in spaces of arbitrary dimensionality and metrics with any signatures. In the two-dimensional case illustrations and animations can be produced.
plane-geometry  construction  rather-interesting  constructibility  library  software  representation  nudge-targets  consider:looking-to-see  computational-geometry
october 2017 by Vaguery
[1709.06021] A Novel Approach for Ellipsoidal Outer-Approximation of the Intersection Region of Ellipses in the Plane
In this paper, a novel technique for tight outer-approximation of the intersection region of a finite number of ellipses in 2-dimensional (2D) space is proposed. First, the vertices of a tight polygon that contains the convex intersection of the ellipses are found in an efficient manner. To do so, the intersection points of the ellipses that fall on the boundary of the intersection region are determined, and a set of points is generated on the elliptic arcs connecting every two neighbouring intersection points. By finding the tangent lines to the ellipses at the extended set of points, a set of half-planes is obtained, whose intersection forms a polygon. To find the polygon more efficiently, the points are given an order and the intersection of the half-planes corresponding to every two neighbouring points is calculated. If the polygon is convex and bounded, these calculated points together with the initially obtained intersection points will form its vertices. If the polygon is non-convex or unbounded, we can detect this situation and then generate additional discrete points only on the elliptical arc segment causing the issue, and restart the algorithm to obtain a bounded and convex polygon. Finally, the smallest area ellipse that contains the vertices of the polygon is obtained by solving a convex optimization problem. Through numerical experiments, it is illustrated that the proposed technique returns a tighter outer-approximation of the intersection of multiple ellipses, compared to conventional techniques, with only slightly higher computational cost.
computational-geometry  algorithms  optimization  computational-complexity  rather-interesting  nudge-targets  consider:looking-to-see
october 2017 by Vaguery
[1710.00386] Orthogonal Terrain Guarding is NP-complete
A terrain is an x-monotone polygonal curve, i.e., successive vertices have increasing x-coordinates. Terrain Guarding can be seen as a special case of the famous art gallery problem where one has to place at most k guards on a terrain made of n vertices in order to fully see it. In 2010, King and Krohn showed that Terrain Guarding is NP-complete [SODA '10, SIAM J. Comput. '11] thereby solving a long-standing open question. They observe that their proof does not settle the complexity of Orthogonal Terrain Guarding where the terrain only consists of horizontal or vertical segments; those terrains are called rectilinear or orthogonal. Recently, Ashok et al. [SoCG'17] presented an FPT algorithm running in time kO(k)nO(1) for Dominating Set in the visibility graphs of rectilinear terrains without 180-degree vertices. They ask if Orthogonal Terrain Guarding is in P or NP-hard. In the same paper, they give a subexponential-time algorithm running in nO(n√) (actually even nO(k√)) for the general Terrain Guarding and notice that the hardness proof of King and Krohn only disproves a running time 2o(n1/4) under the ETH. Hence, there is a significant gap between their 2O(n1/2logn)-algorithm and the no 2o(n1/4) ETH-hardness implied by King and Krohn's result. In this paper, we answer those two remaining questions. We adapt the gadgets of King and Krohn to rectilinear terrains in order to prove that even Orthogonal Terrain Guarding is NP-complete. Then, we show how their reduction from Planar 3-SAT (as well as our adaptation for rectilinear terrains) can actually be made linear (instead of quadratic).
computational-complexity  computational-geometry  proof  consider:stress-testing  nudge-targets  consider:hardest-problems  to-write-about
october 2017 by Vaguery
[cs/0302027] Tiling space and slabs with acute tetrahedra
We show it is possible to tile three-dimensional space using only tetrahedra with acute dihedral angles. We present several constructions to achieve this, including one in which all dihedral angles are less than 77.08∘, and another which tiles a slab in space.
computational-geometry  tiling  rather-interesting  constraint-satisfaction  nudge-targets  consider:feature-discovery  consider:simpler-planar-problem
october 2017 by Vaguery
[1605.04550] Finite-size effects and percolation properties of Poisson geometries
Random tessellations of the space represent a class of prototype models of heterogeneous media, which are central in several applications in physics, engineering and life sciences. In this work, we investigate the statistical properties of d-dimensional isotropic Poisson geometries by resorting to Monte Carlo simulation, with special emphasis on the case d=3. We first analyse the behaviour of the key features of these stochastic geometries as a function of the dimension d and the linear size L of the domain. Then, we consider the case of Poisson binary mixtures, where the polyhedra are assigned two `labels' with complementary probabilities. For this latter class of random geometries, we numerically characterize the percolation threshold, the strength of the percolating cluster and the average cluster size.
probability-theory  computational-geometry  statistical-mechanics  looking-to-see  simulation  rather-interesting  feature-extraction  to-write-about
october 2017 by Vaguery
[1610.03839] Variational approximation of functionals defined on 1-dimensional connected sets: the planar case
In this paper we consider variational problems involving 1-dimensional connected sets in the euclidean plane, such as the classical Steiner tree problem and the irrigation (Gilbert-Steiner) problem. We relate them to optimal partition problems and provide a variational approximation through Modica-Mortola type energies proving a full Γ-convergence result. We also introduce a suitable convex relaxation and develop the corresponding numerical implementations. The proposed methods are quite general and the results we obtain can be extended to n-dimensional euclidean space or to more general manifold ambients, as shown in the companion paper [11].
optimization  operations-research  computational-geometry  continuous-functions  algorithms  relaxations  rather-interesting  nudge-targets  consider:rediscovery
october 2017 by Vaguery
[1708.02891v1] Area difference bounds for dissections of a square into an odd number of triangles
Monsky's theorem from 1970 states that a square cannot be dissected into an odd number of triangles of the same area, but it does not give a lower bound for the area differences that must occur.
We extend Monsky's theorem to "constrained framed maps"; based on this we can apply a gap theorem from semi-algebraic geometry to a polynomial area difference measure and thus get a lower bound for the area differences that decreases doubly-exponentially with the number of triangles. On the other hand, we obtain the first superpolynomial upper bounds for this problem, derived from an explicit construction that uses the Thue-Morse sequence.
computational-geometry  limits  geometry  constraint-satisfaction  nudge-targets  consider:looking-to-see  consider:representation  to-write-about
september 2017 by Vaguery
[1701.05290] Range-efficient consistent sampling and locality-sensitive hashing for polygons
Locality-sensitive hashing (LSH) is a fundamental technique for similarity search and similarity estimation in high-dimensional spaces. The basic idea is that similar objects should produce hash collisions with probability significantly larger than objects with low similarity. We consider LSH for objects that can be represented as point sets in either one or two dimensions. To make the point sets finite size we consider the subset of points on a grid. Directly applying LSH (e.g. min-wise hashing) to these point sets would require time proportional to the number of points. We seek to achieve time that is much lower than direct approaches.
Technically, we introduce new primitives for range-efficient consistent sampling (of independent interest), and show how to turn such samples into LSH values. Another application of our technique is a data structure for quickly estimating the size of the intersection or union of a set of preprocessed polygons. Curiously, our consistent sampling method uses transformation to a geometric problem.
rather-interesting  approximation  representation  to-understand  nudge  consider:for-behavior-classification  to-write-about  computational-geometry
september 2017 by Vaguery
[1704.00264] Potential Functions based Sampling Heuristic For Optimal Path Planning
Rapidly-exploring Random Tree Star(RRT*) is a recently proposed extension of Rapidly-exploring Random Tree (RRT) algorithm that provides a collision-free, asymptotically optimal path regardless of obstacle's geometry in a given environment. However, one of the limitations in the RRT* algorithm is slow convergence to optimal path solution. As a result, it consumes high memory as well as time due to a large number of iterations utilised in achieving optimal path solution. To overcome these limitations, we propose the Potential Function Based-RRT* (P-RRT*) that incorporates the Artificial Potential Field Algorithm in RRT*. The proposed algorithm allows a considerable decrease in the number of iterations and thus leads to more efficient memory utilization and an accelerated convergence rate. In order to illustrate the usefulness of the proposed algorithm in terms of space execution and convergence rate, this paper presents rigorous simulation based comparisons between the proposed techniques and RRT* under different environmental conditions. Moreover, both algorithms are also tested and compared under non-holonomic differential constraints.
planning  representation  robotics  computational-geometry  heuristics  rather-interesting  to-write-about  consider:looking-to-see  consider:simplifying
september 2017 by Vaguery
[1606.02220] Non-aligned drawings of planar graphs
A non-aligned drawing of a graph is a drawing where no two vertices are in the same row or column. Auber et al. showed that not all planar graphs have non-aligned drawings that are straight-line, planar, and in the minimal-possible n×n-grid. They also showed that such drawings exist if up to n−3 edges may have a bend. In this paper, we give algorithms for non-aligned planar drawings that improve on the results by Auber et al. In particular, we give such drawings in an n×n-grid with significantly fewer bends, and we study what grid-size can be achieved if we insist on having straight-line drawings
graph-layout  computational-geometry  algorithms  constraint-satisfaction  rather-interesting  to-write-about  multiobjective-optimization  nudge-targets  consider:feature-discovery
september 2017 by Vaguery
[1708.09560] A Note on Plus-Contacts, Rectangular Duals, and Box-Orthogonal Drawings
A plus-contact representation of a planar graph G is called c-balanced if for every plus shape +v, the number of other plus shapes incident to each arm of +v is at most cΔ+O(1), where Δ is the maximum degree of G. Although small values of c have been achieved for a few subclasses of planar graphs (e.g., 2- and 3-trees), it is unknown whether c-balanced representations with c<1 exist for arbitrary planar graphs.
In this paper we compute (1/2)-balanced plus-contact representations for all planar graphs that admit a rectangular dual. Our result implies that any graph with a rectangular dual has a 1-bend box-orthogonal drawings such that for each vertex v, the box representing v is a square of side length deg(v)2+O(1).
computational-geometry  graph-layout  multiobjective-optimization  rather-interesting  nudge-targets  consider:looking-to-see  consider:rediscovery
september 2017 by Vaguery
[math/9410209] Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms
This paper describes a general-purpose programming technique, called the Simulation of Simplicity, which can be used to cope with degenerate input data for geometric algorithms. It relieves the programmer from the task to provide a consistent treatment for every single special case that can occur. The programs that use the technique tend to be considerably smaller and more robust than those that do not use it. We believe that this technique will become a standard tool in writing geometric software.
geometry  algorithms  computational-geometry  rather-interesting  to-write-about  consider:kata
september 2017 by Vaguery
[1502.02053] Negative refraction and tiling billiards
We introduce a new dynamical system that we call "tiling billiards," where trajectories refract through planar tilings. This system is motivated by a recent discovery of physical substances with negative indices of refraction. We investigate several special cases where the planar tiling is created by dividing the plane by lines, and we describe the results of computer experiments.
tiling  dynamical-systems  billiards  computational-geometry  rather-interesting  mathematical-recreations  to-write-about
september 2017 by Vaguery
[1709.07797] Intrinsic Metrics: Nearest Neighbor and Edge Squared Distances
Some researchers have proposed using non-Euclidean metrics for clustering data points. Generally, the metric should recognize that two points in the same cluster are close, even if their Euclidean distance is far. Multiple proposals have been suggested, including the Edge-Squared Metric (a specific example of a graph geodesic) and the Nearest Neighbor Metric.
In this paper, we prove that the edge-squared and nearest-neighbor metrics are in fact equivalent. Previous best work showed that the edge-squared metric was a 3-approximation of the Nearest Neighbor metric. This paper represents one of the first proofs of equating a continuous metric with a discrete metric, using non-trivial discrete methods. Our proof uses the Kirszbraun theorem (also known as the Lipschitz Extension Theorem and Brehm's Extension Theorem), a notable theorem in functional analysis and computational geometry.
The results of our paper, combined with the results of Hwang, Damelin, and Hero, tell us that the Nearest Neighbor distance on i.i.d samples of a density is a reasonable constant approximation of a natural density-based distance function.
clustering  metrics  statistics  amusing  one-of-these-things-is-just-like-the-other  computational-geometry
september 2017 by Vaguery
[1608.08324] Topological Drawings of Complete Bipartite Graphs
Topological drawings are natural representations of graphs in the plane, where vertices are represented by points, and edges by curves connecting the points. Topological drawings of complete graphs and of complete bipartite graphs have been studied extensively in the context of crossing number problems. We consider a natural class of simple topological drawings of complete bipartite graphs, in which we require that one side of the vertex set bipartition lies on the outer boundary of the drawing.
We investigate the combinatorics of such drawings. For this purpose, we define combinatorial encodings of the drawings by enumerating the distinct drawings of subgraphs isomorphic to K2,2 and K3,2, and investigate the constraints they must satisfy. We prove that a drawing of Kk,n exists if and only if some simple local conditions are satisfied by the encodings. This directly yields a polynomial-time algorithm for deciding the existence of such a drawing given the encoding. We show the encoding is equivalent to specifying which pairs of edges cross, yielding a similar polynomial-time algorithm for the realizability of abstract topological graphs.
We also completely characterize and enumerate such drawings of Kk,n in which the order of the edges around each vertex is the same for vertices on the same side of the bipartition. Finally, we investigate drawings of Kk,n using straight lines and pseudolines, and consider the complexity of the corresponding realizability problems.
computational-geometry  graph-layout  rather-interesting  purdy-pitchers  nudge-targets  consider:representation  consider:performance-measures
september 2017 by Vaguery
[1604.07099] On Guarding Orthogonal Polygons with Sliding Cameras
A sliding camera inside an orthogonal polygon P is a point guard that travels back and forth along an orthogonal line segment γ in P. The sliding camera g can see a point p in P if the perpendicular from p onto γ is inside P. In this paper, we give the first constant-factor approximation algorithm for the problem of guarding P with the minimum number of sliding cameras. Next, we show that the sliding guards problem is linear-time solvable if the (suitably defined) dual graph of the polygon has bounded treewidth. Finally, we study art gallery theorems for sliding cameras, thus, give upper and lower bounds in terms of the number of guards needed relative to the number of vertices n.
computational-geometry  constraint-satisfaction  planning  rather-interesting  nudge-targets  consider:looking-to-see
september 2017 by Vaguery
[cs/9909001] Emerging Challenges in Computational Topology
Here we present the results of the NSF-funded Workshop on Computational Topology, which met on June 11 and 12 in Miami Beach, Florida. This report identifies important problems involving both computation and topology.
september 2017 by Vaguery
[1212.0649] Optimal packings of congruent circles on a square flat torus
We consider packings of congruent circles on a square flat torus, i.e., periodic (w.r.t. a square lattice) planar circle packings, with the maximal circle radius. This problem is interesting due to a practical reason - the problem of "super resolution of images." We have found optimal arrangements for N=6, 7 and 8 circles. Surprisingly, for the case N=7 there are three different optimal arrangements. Our proof is based on a computer enumeration of toroidal irreducible contact graphs.
packing  computational-geometry  optimization  to-write-about  nudge-targets  consider:looking-to-see  consider:feature-discovery  plane-geometry
september 2017 by Vaguery
[1709.01456] Improved Bounds for Drawing Trees on Fixed Points with L-shaped Edges
Let T be an n-node tree of maximum degree 4, and let P be a set of n points in the plane with no two points on the same horizontal or vertical line. It is an open question whether T always has a planar drawing on P such that each edge is drawn as an orthogonal path with one bend (an "L-shaped" edge). By giving new methods for drawing trees, we improve the bounds on the size of the point set P for which such drawings are possible to: O(n1.55) for maximum degree 4 trees; O(n1.22) for maximum degree 3 (binary) trees; and O(n1.142) for perfect binary trees.
Drawing ordered trees with L-shaped edges is harder---we give an example that cannot be done and a bound of O(nlogn) points for L-shaped drawings of ordered caterpillars, which contrasts with the known linear bound for unordered caterpillars.
graph-layout  computational-geometry  algorithms  rather-interesting  representation  visualization  hard-problems  nudge-targets  constraint-satisfaction  consider:feature-discovery
september 2017 by Vaguery
[1705.08735] Weighted Poisson-Delaunay Mosaics
Slicing a Voronoi tessellation in ℝn with a k-plane gives a k-dimensional weighted Voronoi tessellation, also known as power diagram or Laguerre tessellation. Mapping every simplex of the dual weighted Delaunay mosaic to the radius of the smallest empty circumscribed sphere whose center lies in the k-plane gives a generalized discrete Morse function. Assuming the Voronoi tessellation is generated by a Poisson point process in ℝn, we study the expected number of simplices in the k-dimensional weighted Delaunay mosaic as well as the expected number of intervals of the Morse function, both as functions of a radius threshold.
computational-geometry  algorithms  tiling  probability-theory  to-understand  to-write-about
september 2017 by Vaguery
[1705.00924] Split Packing: Algorithms for Packing Circles with Optimal Worst-Case Density
In the circle packing problem for triangular containers, one asks whether a given set of circles can be packed into a given triangle. Packing problems like this have been shown to be 𝖭𝖯-hard. In this paper, we present a new sufficient condition for packing circles into any right or obtuse triangle using only the circles' combined area: It is possible to pack any circle instance whose combined area does not exceed the triangle's incircle. This area condition is tight, in the sense that for any larger area, there are instances which cannot be packed.
A similar result for square containers has been established earlier this year, using the versatile, divide-and-conquer-based Split Packing algorithm. In this paper, we present a generalized, weighted version of this approach, allowing us to construct packings of circles into asymmetric triangles. It seems crucial to the success of these results that Split Packing does not depend on an orthogonal subdivision structure. Beside realizing all packings below the critical density bound, our algorithm can also be used as a constant-factor approximation algorithm when looking for the smallest non-acute triangle of a given side ratio in which a given set of circles can be packed.
An interactive visualization of the Split Packing approach and other related material can be found at this https URL
packing  computational-complexity  computational-geometry  experiment  rather-interesting  to-write-about
june 2017 by Vaguery
[1703.01350] Approximate Convex Hulls
We investigate the PPI algorithm as a means for computing ap- proximate convex hull. We explain how the algorithm computes the curvature of points and prove consistency and convergence. We also extend the algorithm to compute approximate convex hulls described in terms of hyperplanes.
may 2017 by Vaguery
[1410.3564v1] Randomized Triangle Algorithms for Convex Hull Membership
We present randomized versions of the {\it triangle algorithm} introduced in \cite{kal14}. The triangle algorithm tests membership of a distinguished point p∈ℝm in the convex hull of a given set S of n points in ℝm. Given any {\it iterate} p′∈conv(S), it searches for a {\it pivot}, a point v∈S so that d(p′,v)≥d(p,v). It replaces p′ with the point on the line segment p′v closest to p and repeats this process. If a pivot does not exist, p′ certifies that p∉conv(S). Here we propose two random variations of the triangle algorithm that allow relaxed steps so as to take more effective steps possible in subsequent iterations. One is inspired by the {\it chaos game} known to result in the Sierpinski triangle. The incentive is that randomized iterates together with a property of Sierpinski triangle would result in effective pivots. Bounds on their expected complexity coincides with those of the deterministic version derived in \cite{kal14}.
computational-geometry  algorithms  convex-hulls  rather-interesting  nudge-targets  consider:representation  consider:looking-to-see
may 2017 by Vaguery
[1608.08844] Snapping Graph Drawings to the Grid Optimally
In geographic information systems and in the production of digital maps for small devices with restricted computational resources one often wants to round coordinates to a rougher grid. This removes unnecessary detail and reduces space consumption as well as computation time. This process is called snapping to the grid and has been investigated thoroughly from a computational-geometry perspective. In this paper we investigate the same problem for given drawings of planar graphs under the restriction that their combinatorial embedding must be kept and edges are drawn straight-line. We show that the problem is NP-hard for several objectives and provide an integer linear programming formulation. Given a plane graph G and a positive integer w, our ILP can also be used to draw G straight-line on a grid of width w and minimum height (if possible).
graph-layout  computational-geometry  algorithms  rather-interesting  constraint-satisfaction  nudge-targets  consider:looking-to-see  approximation  performance-measure
may 2017 by Vaguery
[1409.0499] Drawing Graphs within Restricted Area
We study the problem of selecting a maximum-weight subgraph of a given graph such that the subgraph can be drawn within a prescribed drawing area subject to given non-uniform vertex sizes. We develop and analyze heuristics both for the general (undirected) case and for the use case of (directed) calculation graphs which are used to analyze the typical mistakes that high school students make when transforming mathematical expressions in the process of calculating, for example, sums of fractions.
graph-layout  constraint-satisfaction  multiobjective-optimization  computational-geometry  parametrization  to-write-about  aesthetics
may 2017 by Vaguery
[1305.0750] Multi-Sided Boundary Labeling
In the Boundary Labeling problem, we are given a set of n points, referred to as sites, inside an axis-parallel rectangle R, and a set of n pairwise disjoint rectangular labels that are attached to R from the outside. The task is to connect the sites to the labels by non-intersecting rectilinear paths, so-called leaders, with at most one bend.
In this paper, we study the Multi-Sided Boundary Labeling problem, with labels lying on at least two sides of the enclosing rectangle. We present a polynomial-time algorithm that computes a crossing-free leader layout if one exists. So far, such an algorithm has only been known for the cases in which labels lie on one side or on two opposite sides of R (here a crossing-free solution always exists). The case where labels may lie on adjacent sides is more difficult. We present efficient algorithms for testing the existence of a crossing-free leader layout that labels all sites and also for maximizing the number of labeled sites in a crossing-free leader layout. For two-sided boundary labeling with adjacent sides, we further show how to minimize the total leader length in a crossing-free layout.
computational-geometry  graph-layout  maps  constraint-satisfaction  multiobjective-optimization  performance-measure  rather-interesting  engineering-philosophy  to-write-about  good-examples-for-MO
may 2017 by Vaguery
[1209.0830] Progress on Partial Edge Drawings
Recently, a new way of avoiding crossings in straight-line drawings of non-planar graphs has been investigated. The idea of partial edge drawings (PED) is to drop the middle part of edges and rely on the remaining edge parts called stubs. We focus on a symmetric model (SPED) that requires the two stubs of an edge to be of equal length. In this way, the stub at the other endpoint of an edge assures the viewer of the edge's existence. We also consider an additional homogeneity constraint that forces the stub lengths to be a given fraction δ of the edge lengths (δ-SHPED). Given length and direction of a stub, this model helps to infer the position of the opposite stub.
We show that, for a fixed stub--edge length ratio δ, not all graphs have a δ-SHPED. Specifically, we show that K241 does not have a 1/4-SHPED, while bandwidth-k graphs always have a Θ(1/k√)-SHPED. We also give bounds for complete bipartite graphs. Further, we consider the problem \textsc{MaxSPED} where the task is to compute the SPED of maximum total stub length that a given straight-line drawing contains. We present an efficient solution for 2-planar drawings and a 2-approximation algorithm for the dual problem.
graph-layout  computational-geometry  algorithms  constraint-satisfaction  rather-interesting  representation  to-write-about
may 2017 by Vaguery
[0806.0253] On collinear sets in straight line drawings
We consider straight line drawings of a planar graph G with possible edge crossings. The \emph{untangling problem} is to eliminate all edge crossings by moving as few vertices as possible to new positions. Let fix(G) denote the maximum number of vertices that can be left fixed in the worst case. In the \emph{allocation problem}, we are given a planar graph G on n vertices together with an n-point set X in the plane and have to draw G without edge crossings so that as many vertices as possible are located in X. Let fit(G) denote the maximum number of points fitting this purpose in the worst case. As fix(G)≤fit(G), we are interested in upper bounds for the latter and lower bounds for the former parameter.
For each ϵ>0, we construct an infinite sequence of graphs with fit(G)=O(nσ+ϵ), where σ<0.99 is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. To the best of our knowledge, this is the first example of graphs with fit(G)=o(n). On the other hand, we prove that fix(G)≥n/30‾‾‾‾√ for all G with tree-width at most 2. This extends the lower bound obtained by Goaoc et al. [Discrete and Computational Geometry 42:542-569 (2009)] for outerplanar graphs.
Our upper bound for fit(G) is based on the fact that the constructed graphs can have only few collinear vertices in any crossing-free drawing. To prove the lower bound for fix(G), we show that graphs of tree-width 2 admit drawings that have large sets of collinear vertices with some additional special properties.
graph-theory  computational-geometry  graph-layout  algorithms  rather-interesting  nudge-targets  consider:mathematical-recreations  consider:classification
may 2017 by Vaguery
[1607.01196] Drawing Graphs on Few Lines and Few Planes
We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows.
We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values.
We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing).
We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane.
graph-layout  computational-geometry  optimization  graph-theory  topology  rather-interesting  to-write-about  consider:feature-discovery  nudge-targets  consider:classification
may 2017 by Vaguery
[1607.06136] Eliminating Depth Cycles among Triangles in Three Dimensions
Given n non-vertical pairwise disjoint triangles in 3-space, their vertical depth (above/below) relation may contain cycles. We show that, for any ε>0, the triangles can be cut into O(n3/2+ε) pieces, where each piece is a connected semi-algebraic set whose description complexity depends only on the choice of ε, such that the depth relation among these pieces is now a proper partial order. This bound is nearly tight in the worst case. We are not aware of any previous study of this problem with a subquadratic bound on the number of pieces.
This work extends the recent study by two of the authors on eliminating depth cycles among lines in 3-space. Our approach is again algebraic, and makes use of a recent variant of the polynomial partitioning technique, due to Guth, which leads to a recursive procedure for cutting the triangles. In contrast to the case of lines, our analysis here is considerably more involved, due to the two-dimensional nature of the objects being cut, so additional tools, from topology and algebra, need to be brought to bear.
Our result essentially settles a 35-year-old open problem in computational geometry, motivated by hidden-surface removal in computer graphics.
computational-geometry  algorithms  hidden-line-removal  rather-interesting  computational-complexity  constraint-satisfaction  nudge-targets  consider:rediscovery
may 2017 by Vaguery
[1201.2097v4] Partial Searchlight Scheduling is Strongly PSPACE-Complete
The problem of searching a polygonal region for an unpredictably moving intruder by a set of stationary guards, each carrying an orientable laser, is known as the Searchlight Scheduling Problem. Determining the computational complexity of deciding if the polygon can be searched by a given set of guards is a long-standing open problem.
Here we propose a generalization called the Partial Searchlight Scheduling Problem, in which only a given subregion of the environment has to be searched, as opposed to the entire area. We prove that the corresponding decision problem is strongly PSPACE-complete, both in general and restricted to orthogonal polygons where the region to be searched is a rectangle.
Our technique is to reduce from the "edge-to-edge" problem for nondeterministic constraint logic machines, after showing that the computational power of such machines does not change if we allow "asynchronous" edge reversals (as opposed to "sequential").
computational-geometry  computational-complexity  planning  art-gallery-problems  proof  nudge-targets
april 2017 by Vaguery
[1701.05475] Irrational Guards are Sometimes Needed
In this paper we study the art gallery problem, which is one of the fundamental problems in computational geometry. The objective is to place a minimum number of guards inside a simple polygon such that the guards together can see the whole polygon. We say that a guard at position x sees a point y if the line segment xy is fully contained in the polygon.
Despite an extensive study of the art gallery problem, it remained an open question whether there are polygons given by integer coordinates that require guard positions with irrational coordinates in any optimal solution. We give a positive answer to this question by constructing a monotone polygon with integer coordinates that can be guarded by three guards only when we allow to place the guards at points with irrational coordinates. Otherwise, four guards are needed. By extending this example, we show that for every n, there is polygon which can be guarded by 3n guards with irrational coordinates but need 4n guards if the coordinates have to be rational. Subsequently, we show that there are rectilinear polygons given by integer coordinates that require guards with irrational coordinates in any optimal solution.
computational-complexity  computational-geometry  planning  art-gallery-problems  algorithms  proof  rather-interesting  nudge-targets  to-write-about
april 2017 by Vaguery
[1405.1894] Halving Balls in Deterministic Linear Time
Let $\D$ be a set of n pairwise disjoint unit balls in $\R^d$ and P the set of their center points. A hyperplane $\Hy$ is an \emph{m-separator} for $\D$ if each closed halfspace bounded by $\Hy$ contains at least m points from P. This generalizes the notion of halving hyperplanes, which correspond to n/2-separators. The analogous notion for point sets has been well studied. Separators have various applications, for instance, in divide-and-conquer schemes. In such a scheme any ball that is intersected by the separating hyperplane may still interact with both sides of the partition. Therefore it is desirable that the separating hyperplane intersects a small number of balls only. We present three deterministic algorithms to bisect or approximately bisect a given set of disjoint unit balls by a hyperplane: Firstly, we present a simple linear-time algorithm to construct an αn-separator for balls in $\R^d$, for any 0<α<1/2, that intersects at most cn(d−1)/d balls, for some constant c that depends on d and α. The number of intersected balls is best possible up to the constant c. Secondly, we present a near-linear time algorithm to construct an (n/2−o(n))-separator in $\R^d$ that intersects o(n) balls. Finally, we give a linear-time algorithm to construct a halving line in $\R^2$ that intersects O(n(5/6)+ϵ) disks.
Our results improve the runtime of a disk sliding algorithm by Bereg, Dumitrescu and Pach. In addition, our results improve and derandomize an algorithm to construct a space decomposition used by L{\"o}ffler and Mulzer to construct an onion (convex layer) decomposition for imprecise points (any point resides at an unknown location within a given disk).
computational-geometry  computational-complexity  algorithms  nudge-targets  consider:rediscovery
april 2017 by Vaguery
per page:    204080120160

Copy this bookmark:

description:

tags: