**Vaguery + computational-geometry**
366

[1807.09977] Colored range closest-pair problem under general distance functions

7 days ago by Vaguery

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

7 days ago by Vaguery

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
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.

7 days ago by Vaguery

[1809.07481] $L_1$ Shortest Path Queries in Simple Polygons

17 days ago by Vaguery

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

17 days ago by Vaguery

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
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.

17 days ago by Vaguery

[1706.08105] Compatible 4-Holes in Point Sets

21 days ago by Vaguery

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

22 days ago by Vaguery

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

22 days ago by Vaguery

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
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.

22 days ago by Vaguery

Largest and Smallest Convex Hulls for Imprecise Points | SpringerLink

27 days ago by Vaguery

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

27 days ago by Vaguery

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

27 days ago by Vaguery

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

27 days ago by Vaguery

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

27 days ago by Vaguery

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

27 days ago by Vaguery

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
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.

27 days ago by Vaguery

[1512.04349] Clustering time series under the Fr'echet distance

6 weeks ago by Vaguery

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
Keywords: time series, longitudinal data, functional data, clustering, Fréchet distance, dynamic time warping, approximation algorithms.

6 weeks ago by Vaguery

Fréchet distance - Wikipedia

6 weeks ago by Vaguery

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

[1801.08003] Threadable Curves

october 2018 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 moving sofa problem — Dan Romik's home page

april 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

march 2018 by Vaguery

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
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.

march 2018 by Vaguery

[1802.06415] Solving Large-Scale Minimum-Weight Triangulation Instances to Provable Optimality

march 2018 by Vaguery

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

february 2018 by Vaguery

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

About the Journal

february 2018 by Vaguery

fully open-access journal with explicit integration into distributed scholarly archives and libraries

computational-geometry
open-access
publishing
to-write-about
to-do
february 2018 by Vaguery

[1712.02657] Generalised primal-dual grids for unstructured co-volume schemes

january 2018 by Vaguery

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

december 2017 by Vaguery

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

november 2017 by Vaguery

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
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.

november 2017 by Vaguery

[1711.02450] Shape Representation by Zippable Ribbons

november 2017 by Vaguery

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.

via:gigasquid
computational-geometry
construction
manufacturability
representation
algorithms
to-write-about
via:twitter
topology
november 2017 by Vaguery

[1308.5550] Fitting Voronoi Diagrams to Planar Tesselations

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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
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.

november 2017 by Vaguery

[1405.2378] Covering Folded Shapes

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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

november 2017 by Vaguery

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
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.

november 2017 by Vaguery

[0705.4085] The Distance Geometry of Music

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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.

computational-geometry
rather-interesting
to-write-about
mathematical-recreations
consider:looking-to-see
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

october 2017 by Vaguery

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
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.

october 2017 by Vaguery

[1604.07134] New minimal (4,n)-regular matchstick graphs

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

october 2017 by Vaguery

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

september 2017 by Vaguery

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
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.

september 2017 by Vaguery

[1701.05290] Range-efficient consistent sampling and locality-sensitive hashing for polygons

september 2017 by Vaguery

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
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.

september 2017 by Vaguery

[1704.00264] Potential Functions based Sampling Heuristic For Optimal Path Planning

september 2017 by Vaguery

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

september 2017 by Vaguery

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

september 2017 by Vaguery

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
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).

september 2017 by Vaguery

[math/9410209] Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms

september 2017 by Vaguery

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

september 2017 by Vaguery

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

september 2017 by Vaguery

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
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.

september 2017 by Vaguery

[1608.08324] Topological Drawings of Complete Bipartite Graphs

september 2017 by Vaguery

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
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.

september 2017 by Vaguery

[1604.07099] On Guarding Orthogonal Polygons with Sliding Cameras

september 2017 by Vaguery

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

september 2017 by Vaguery

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.

computational-geometry
conference
proceedings
to-read
open-questions
september 2017 by Vaguery

[1212.0649] Optimal packings of congruent circles on a square flat torus

september 2017 by Vaguery

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

september 2017 by Vaguery

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
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.

september 2017 by Vaguery

[1705.08735] Weighted Poisson-Delaunay Mosaics

september 2017 by Vaguery

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

june 2017 by Vaguery

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
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

june 2017 by Vaguery

[1703.01350] Approximate Convex Hulls

may 2017 by Vaguery

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.

computational-geometry
approximation
algorithms
rather-interesting
to-write-about
may 2017 by Vaguery

[1410.3564v1] Randomized Triangle Algorithms for Convex Hull Membership

may 2017 by Vaguery

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

may 2017 by Vaguery

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

may 2017 by Vaguery

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

may 2017 by Vaguery

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
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.

may 2017 by Vaguery

[1209.0830] Progress on Partial Edge Drawings

may 2017 by Vaguery

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
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.

may 2017 by Vaguery

[0806.0253] On collinear sets in straight line drawings

may 2017 by Vaguery

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
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.

may 2017 by Vaguery

[1607.01196] Drawing Graphs on Few Lines and Few Planes

may 2017 by Vaguery

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
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.

may 2017 by Vaguery

[1607.06136] Eliminating Depth Cycles among Triangles in Three Dimensions

may 2017 by Vaguery

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
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.

may 2017 by Vaguery

[1201.2097v4] Partial Searchlight Scheduling is Strongly PSPACE-Complete

april 2017 by Vaguery

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
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").

april 2017 by Vaguery

[1701.05475] Irrational Guards are Sometimes Needed

april 2017 by Vaguery

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
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.

april 2017 by Vaguery

[1405.1894] Halving Balls in Deterministic Linear Time

april 2017 by Vaguery

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
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).

april 2017 by Vaguery

**related tags**

Copy this bookmark: