We consider the construction of a polygon P with n vertices whose turning angles at the vertices are given by a sequence A = (α0 , . . . , αn−1 ), αi ∈ (−π,π), for i ∈ {0,...,n − 1}. The problem of realizing A by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an angle graph. In 2D, we characterize sequences A for which every generic polygon P ⊂ R2 realizing A has at least c crossings, and describe an efficient algorithm that constructs, for a given sequence A, a generic polygon P ⊂ R2 that realizes A with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence A can be realized by a (not necessarily generic) polygon P ⊂ R3, and for every realizable sequence finds a realization.
more »
« less
Polygons with Prescribed Angles in 2D and 3D
We consider the construction of a polygon P with n vertices whose turning angles at the vertices are given by a sequence A=(α0,…,αn−1) , αi∈(−π,π) , for i∈{0,…,n−1} . The problem of realizing A by a polygon can be seen as that of constructing a straight-line drawing of a graph with prescribed angles at vertices, and hence, it is a special case of the well studied problem of constructing an angle graph. In 2D, we characterize sequences A for which every generic polygon P⊂R2 realizing A has at least c crossings, for every c∈N , and describe an efficient algorithm that constructs, for a given sequence A, a generic polygon P⊂R2 that realizes A with the minimum number of crossings. In 3D, we describe an efficient algorithm that tests whether a given sequence A can be realized by a (not necessarily generic) polygon P⊂R3 , and for every realizable sequence the algorithm finds a realization.
more »
« less
- Award ID(s):
- 1800734
- NSF-PAR ID:
- 10253545
- Date Published:
- Journal Name:
- Graph Drawing and Network Visualization
- Volume:
- 12590
- Page Range / eLocation ID:
- 135-147
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Let f be a drawing in the Euclidean plane of a graph G, which is understood to be a 1-dimensional simplicial complex. We assume that every edge of G is drawn by f as a curve of constant algebraic complexity, and the ratio of the length of the longest simple path to the the length of the shortest edge is poly(n). In the drawing f, a path P of G, or its image in the drawing π = f(P), is β-stretch if π is a simple (non-self-intersecting) curve, and for every pair of distinct points p ∈ P and q ∈ P , the length of the sub-curve of π connecting f(p) with f(q) is at most β∥f(p) − f(q)∥, where ∥.∥ denotes the Euclidean distance. We introduce and study the β-stretch Path Problem (βSP for short), in which we are given a pair of vertices s and t of G, and we are to decide whether in the given drawing of G there exists a β-stretch path P connecting s and t. We also output P if it exists. The βSP quantifies a notion of “near straightness” for paths in a graph G, motivated by gerrymandering regions in a map, where edges of G represent natural geographical/political boundaries that may be chosen to bound election districts. The notion of a β-stretch path naturally extends to cycles, and the extension gives a measure of how gerrymandered a district is. Furthermore, we show that the extension is closely related to several studied measures of local fatness of geometric shapes. We prove that βSP is strongly NP-complete. We complement this result by giving a quasi-polynomial time algorithm, that for a given ε > 0, β ∈ O(poly(log |V (G)|)), and s, t ∈ V (G), outputs a β-stretch path between s and t, if a (1 − ε)β-stretch path between s and t exists in the drawing.more » « less
-
A spanner of a graph is a subgraph that preserves lengths of shortest paths up to a multiplicative distortion. For every k, a spanner with size O(n^{1+1/k}) and stretch (2k+1) can be constructed by a simple centralized greedy algorithm, and this is tight assuming Erdős girth conjecture. In this paper we study the problem of constructing spanners in a local manner, specifically in the Local Computation Model proposed by Rubinfeld et al. (ICS 2011). We provide a randomized Local Computation Agorithm (LCA) for constructing (2r-1)-spanners with Õ(n^{1+1/r}) edges and probe complexity of Õ(n^{1-1/r}) for r ∈ {2,3}, where n denotes the number of vertices in the input graph. Up to polylogarithmic factors, in both cases, the stretch factor is optimal (for the respective number of edges). In addition, our probe complexity for r = 2, i.e., for constructing a 3-spanner, is optimal up to polylogarithmic factors. Our result improves over the probe complexity of Parter et al. (ITCS 2019) that is Õ(n^{1-1/2r}) for r ∈ {2,3}. Both our algorithms and the algorithms of Parter et al. use a combination of neighbor-probes and pair-probes in the above-mentioned LCAs. For general k ≥ 1, we provide an LCA for constructing O(k²)-spanners with Õ(n^{1+1/k}) edges using O(n^{2/3}Δ²) neighbor-probes, improving over the Õ(n^{2/3}Δ⁴) algorithm of Parter et al. By developing a new randomized LCA for graph decomposition, we further improve the probe complexity of the latter task to be O(n^{2/3-(1.5-α)/k}Δ²), for any constant α > 0. This latter LCA may be of independent interest.more » « less
-
null (Ed.)The problem of sparsifying a graph or a hypergraph while approximately preserving its cut structure has been extensively studied and has many applications. In a seminal work, Benczúr and Karger (1996) showed that given any n-vertex undirected weighted graph G and a parameter ε ∈ (0,1), there is a near-linear time algorithm that outputs a weighted subgraph G' of G of size Õ(n/ε²) such that the weight of every cut in G is preserved to within a (1 ± ε)-factor in G'. The graph G' is referred to as a (1 ± ε)-approximate cut sparsifier of G. Subsequent recent work has obtained a similar result for the more general problem of hypergraph cut sparsifiers. However, all known sparsification algorithms require Ω(n + m) time where n denotes the number of vertices and m denotes the number of hyperedges in the hypergraph. Since m can be exponentially large in n, a natural question is if it is possible to create a hypergraph cut sparsifier in time polynomial in n, independent of the number of edges. We resolve this question in the affirmative, giving the first sublinear time algorithm for this problem, given appropriate query access to the hypergraph. Specifically, we design an algorithm that constructs a (1 ± ε)-approximate cut sparsifier of a hypergraph H(V,E) in polynomial time in n, independent of the number of hyperedges, when given access to the hypergraph using the following two queries: 1) given any cut (S, ̄S), return the size |δ_E(S)| (cut value queries); and 2) given any cut (S, ̄S), return a uniformly at random edge crossing the cut (cut edge sample queries). Our algorithm outputs a sparsifier with Õ(n/ε²) edges, which is essentially optimal. We then extend our results to show that cut value and cut edge sample queries can also be used to construct hypergraph spectral sparsifiers in poly(n) time, independent of the number of hyperedges. We complement the algorithmic results above by showing that any algorithm that has access to only one of the above two types of queries can not give a hypergraph cut sparsifier in time that is polynomial in n. Finally, we show that our algorithmic results also hold if we replace the cut edge sample queries with a pair neighbor sample query that for any pair of vertices, returns a random edge incident on them. In contrast, we show that having access only to cut value queries and queries that return a random edge incident on a given single vertex, is not sufficient.more » « less
-
null (Ed.)Abstract A novel, exact algorithm is presented to solve the path planning problem that involves finding the shortest collision-free path from a start to a goal point in a two-dimensional environment containing convex and non-convex obstacles. The proposed algorithm, which is called the shortest possible path (SPP) algorithm, constructs a network of lines connecting the vertices of the obstacles and the locations of the start and goal points which is smaller than the network generated by the visibility graph. Then it finds the shortest path from start to goal point within this network. The SPP algorithm generates a safe, smooth and obstacle-free path that has a desired distance from each obstacle. This algorithm is designed for environments that are populated sparsely with convex and nonconvex polygonal obstacles. It has the capability of eliminating some of the polygons that do not play any role in constructing the optimal path. It is proven that the SPP algorithm can find the optimal path in O(nn r2 ) time, where n is the number of vertices of all polygons and n ̓ is the number of vertices that are considered in constructing the path network (n ̓ ≤ n). The performance of the algorithm is evaluated relative to three major classes of algorithms: heuristic, probabilistic, and classic. Different benchmark scenarios are used to evaluate the performance of the algorithm relative to the first two classes of algorithms: GAMOPP (genetic algorithm for multi-objective path planning), a representative heuristic algorithm, as well as RRT (rapidly-exploring random tree) and PRM (probabilistic road map), two well-known probabilistic algorithms. Time complexity is known for classic algorithms, so the presented algorithm is compared analytically.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1007/978-3-030-68766-3_11
