Topic overview

Computational Geometry

1083 works2183 researchers0 institutions

Topic snapshot

What this area looks like now

1083works

2183authors

0experts visible

0communities

Next steps

Move from topic reading into action

The graph preview below keeps the nearby papers, people and communities visible in the same reading flow.

Inspect nearby papers, researchers, institutions and communities without opening a separate graph page.

Building this graph slice

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2020arXiv

On Turn-Regular Orthogonal Representations

An interesting class of orthogonal representations consists of the so-called turn-regular ones, i.e., those that do not contain any pair of reflex corners that "point to each other" inside a face. For such a representation H it is possible to compute in linear time a minimum-area drawing, i.e., a drawing of minimum area over all possible assignments of vertex and bend coordinates of H. In contrast, finding a minimum-area drawing of H is NP-hard if H is non-turn-regular. This scenario naturally motivates the study of which graphs admit turn-regular orthogonal representations. In this paper we identify notable classes of biconnected planar graphs that always admit such representations, which can be computed in linear time. We also describe a linear-time testing algorithm for trees and provide a polynomial-time algorithm that tests whether a biconnected plane graph with "small" faces has a turn-regular orthogonal representation without bends.

preprint2020arXiv

On the edge-length ratio of 2-trees

We study planar straight-line drawings of graphs that minimize the ratio between the length of the longest and the shortest edge. We answer a question of Lazard et al. [Theor. Comput. Sci. 770 (2019), 88--94] and, for any given constant $r$, we provide a $2$-tree which does not admit a planar straight-line drawing with a ratio bounded by $r$. When the ratio is restricted to adjacent edges only, we prove that any $2$-tree admits a planar straight-line drawing whose edge-length ratio is at most $4 + \varepsilon$ for any arbitrarily small $\varepsilon > 0$, hence the upper bound on the local edge-length ratio of partial $2$-trees is $4$.

preprint2020arXiv

$2$-Layer $k$-Planar Graphs: Density, Crossing Lemma, Relationships, and Pathwidth

The $2$-layer drawing model is a well-established paradigm to visualize bipartite graphs. Several beyond-planar graph classes have been studied under this model. Surprisingly, however, the fundamental class of $k$-planar graphs has been considered only for $k=1$ in this context. We provide several contributions that address this gap in the literature. First, we show tight density bounds for the classes of $2$-layer $k$-planar graphs with $k\in\{2,3,4,5\}$. Based on these results, we provide a Crossing Lemma for $2$-layer $k$-planar graphs, which then implies a general density bound for $2$-layer $k$-planar graphs. We prove this bound to be almost optimal with a corresponding lower bound construction. Finally, we study relationships between $k$-planarity and $h$-quasiplanarity in the $2$-layer model and show that $2$-layer $k$-planar graphs have pathwidth at most $k+1$.

preprint2020arXiv

Planar Rectilinear Drawings of Outerplanar Graphs in Linear Time

We show how to test in linear time whether an outerplanar graph admits a planar rectilinear drawing, both if the graph has a prescribed plane embedding that the drawing has to respect and if it does not. Our algorithm returns a planar rectilinear drawing if the graph admits one.

preprint2020arXiv

Improved Upper and Lower Bounds for LR Drawings of Binary Trees

In SODA'99, Chan introduced a simple type of planar straight-line upward order-preserving drawings of binary trees, known as LR drawings: such a drawing is obtained by picking a root-to-leaf path, drawing the path as a straight line, and recursively drawing the subtrees along the paths. Chan proved that any binary tree with $n$ nodes admits an LR drawing with $O(n^{0.48})$ width. In SODA'17, Frati, Patrignani, and Roselli proved that there exist families of $n$-node binary trees for which any LR drawing has $Ω(n^{0.418})$ width. In this note, we improve Chan's upper bound to $O(n^{0.437})$ and Frati et al.'s lower bound to $Ω(n^{0.429})$.

preprint2020arXiv

Plane Spanning Trees in Edge-Colored Simple Drawings of $K_n$

Károlyi, Pach, and Tóth proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple drawings of the complete graph. These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once. We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings. (In a cylindrical drawing, all vertices are placed on two concentric circles and no edge crosses either circle.) Second, we introduce a relaxation of the problem in which the graph is $k$-edge-colored, and the target structure must be hypochromatic, that is, avoid (at least) one color class. In this setting, we show that every $\lceil (n+5)/6\rceil$-edge-colored monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree. (In a monotone drawing, every edge is represented as an $x$-monotone curve.)

preprint2020arXiv

Deep Local Shapes: Learning Local SDF Priors for Detailed 3D Reconstruction

Efficiently reconstructing complex and intricate surfaces at scale is a long-standing goal in machine perception. To address this problem we introduce Deep Local Shapes (DeepLS), a deep shape representation that enables encoding and reconstruction of high-quality 3D shapes without prohibitive memory requirements. DeepLS replaces the dense volumetric signed distance function (SDF) representation used in traditional surface reconstruction systems with a set of locally learned continuous SDFs defined by a neural network, inspired by recent work such as DeepSDF. Unlike DeepSDF, which represents an object-level SDF with a neural network and a single latent code, we store a grid of independent latent codes, each responsible for storing information about surfaces in a small local neighborhood. This decomposition of scenes into local shapes simplifies the prior distribution that the network must learn, and also enables efficient inference. We demonstrate the effectiveness and generalization power of DeepLS by showing object shape encoding and reconstructions of full scenes, where DeepLS delivers high compression, accuracy, and local shape completion.

preprint2020arXiv

A Generalization of Self-Improving Algorithms

Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances $x_1,\cdots,x_n$ follow some unknown \emph{product distribution}. That is, $x_i$ comes from a fixed unknown distribution $\mathsf{D}_i$, and the $x_i$'s are drawn independently. After spending $O(n^{1+\varepsilon})$ time in a learning phase, the subsequent expected running time is $O((n+ H)/\varepsilon)$, where $H \in \{H_\mathrm{S},H_\mathrm{DT}\}$, and $H_\mathrm{S}$ and $H_\mathrm{DT}$ are the entropies of the distributions of the sorting and DT output, respectively. In this paper, we allow dependence among the $x_i$'s under the \emph{group product distribution}. There is a hidden partition of $[1,n]$ into groups; the $x_i$'s in the $k$-th group are fixed unknown functions of the same hidden variable $u_k$; and the $u_k$'s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map $u_k$ to $x_i$'s are well-behaved. After an $O(\mathrm{poly}(n))$-time training phase, we achieve $O(n + H_\mathrm{S})$ and $O(nα(n) + H_\mathrm{DT})$ expected r

preprint2020arXiv

Simple Topological Drawings of $k$-Planar Graphs

Every finite graph admits a \emph{simple (topological) drawing}, that is, a drawing where every pair of edges intersects in at most one point. However, in combination with other restrictions simple drawings do not universally exist. For instance, \emph{$k$-planar graphs} are those graphs that can be drawn so that every edge has at most $k$ crossings (i.e., they admit a \emph{$k$-plane drawing}). It is known that for $k\le 3$, every $k$-planar graph admits a $k$-plane simple drawing. But for $k\ge 4$, there exist $k$-planar graphs that do not admit a $k$-plane simple drawing. Answering a question by Schaefer, we show that there exists a function $f : \mathbb{N}\rightarrow\mathbb{N}$ such that every $k$-planar graph admits an $f(k)$-plane simple drawing, for all $k\in\mathbb{N}$. Note that the function $f$ depends on $k$ only and is independent of the size of the graph. Furthermore, we develop an algorithm to show that every $4$-planar graph admits an $8$-plane simple drawing.

preprint2020arXiv

Advancing Through Terrains

We study terrain visibility graphs, a well-known graph class closely related to polygon visibility graphs in computational geometry, for which a precise graph-theoretical characterization is still unknown. Over the last decade, terrain visibility graphs attracted attention in the context of time series analysis with various practical applications in areas such as physics, geography and medical sciences. We make progress in understanding terrain visibility graphs by providing several graph-theoretic results. For example, we show that they cannot contain antiholes of size larger than five. Moreover, we obtain two algorithmic results. We devise a fast output-sensitive shortest path algorithm on terrain-like graphs and a polynomial-time algorithm for \textsc{Dominating Set} on special terrain visibility graphs (called funnel visibility graphs).

preprint2020arXiv

Computing the Real Isolated Points of an Algebraic Hypersurface

Let $\mathbb{R}$ be the field of real numbers. We consider the problem of computing the real isolated points of a real algebraic set in $\mathbb{R}^n$ given as the vanishing set of a polynomial system. This problem plays an important role for studying rigidity properties of mechanism in material designs. In this paper, we design an algorithm which solves this problem. It is based on the computations of critical points as well as roadmaps for answering connectivity queries in real algebraic sets. This leads to a probabilistic algorithm of complexity $(nd)^{O(n\log(n))}$ for computing the real isolated points of real algebraic hypersurfaces of degree $d$. It allows us to solve in practice instances which are out of reach of the state-of-the-art.

preprint2020arXiv

Aligned plane drawings of the generalized Delaunay-graphs for pseudo-disks

We study general Delaunay-graphs, which are natural generalizations of Delaunay triangulations to arbitrary families, in particular to pseudo-disks. We prove that for any finite pseudo-disk family and point set, there is a plane drawing of their Delaunay-graph such that every edge lies inside every pseudo-disk that contains its endpoints.

preprint2020arXiv

Stochastic Gradient Descent Works Really Well for Stress Minimization

Stress minimization is among the best studied force-directed graph layout methods because it reliably yields high-quality layouts. It thus comes as a surprise that a novel approach based on stochastic gradient descent (Zheng, Pawar and Goodman, TVCG 2019) is claimed to improve on state-of-the-art approaches based on majorization. We present experimental evidence that the new approach does not actually yield better layouts, but that it is still to be preferred because it is simpler and robust against poor initialization.

preprint2020arXiv

An Integer-Linear Program for Bend-Minimization in Ortho-Radial Drawings

An ortho-radial grid is described by concentric circles and straight-line spokes emanating from the circles' center. An ortho-radial drawing is the analog of an orthogonal drawing on an ortho-radial grid. Such a drawing has an unbounded outer face and a central face that contains the origin. Building on the notion of an ortho-radial representation (Barth et al., SoCG, 2017), we describe an integer-linear program (ILP) for computing bend-free ortho-radial representations with a given embedding and fixed outer and central face. Using the ILP as a building block, we introduce a pruning technique to compute bend-optimal ortho-radial drawings with a given embedding and a fixed outer face, but freely choosable central face. Our experiments show that, in comparison with orthogonal drawings using the same embedding and the same outer face, the use of ortho-radial drawings reduces the number of bends by 43.8% on average. Further, our approach allows us to compute ortho-radial drawings of embedded graphs such as the metro system of Beijing or London within seconds.

preprint2020arXiv

Limiting crossing numbers for geodesic drawings on the sphere

We introduce a model for random geodesic drawings of the complete bipartite graph $K_{n,n}$ on the unit sphere $\mathbb{S}^2$ in $\mathbb{R}^3$, where we select the vertices in each bipartite class of $K_{n,n}$ with respect to two non-degenerate probability measures on $\mathbb{S}^2$. It has been proved recently that many such measures give drawings whose crossing number approximates the Zarankiewicz number (the conjectured crossing number of $K_{n,n}$). In this paper we consider the intersection graphs associated with such random drawings. We prove that for any probability measures, the resulting random intersection graphs form a convergent graph sequence in the sense of graph limits. The edge density of the limiting graphon turns out to be independent of the two measures as long as they are antipodally symmetric. However, it is shown that the triangle densities behave differently. We examine a specific random model, blow-ups of antipodal drawings $D$ of $K_{4,4}$, and show that the triangle density in the corresponding crossing graphon depends on the angles between the great circles containing the edges in $D$ and can attain any value in the interval $\bigl(\frac{83}{12288}, \fra

preprint2020arXiv

On the Maximum Number of Crossings in Star-Simple Drawings of $K_n$ with No Empty Lens

A star-simple drawing of a graph is a drawing in which adjacent edges do not cross. In contrast, there is no restriction on the number of crossings between two independent edges. When allowing empty lenses (a face in the arrangement induced by two edges that is bounded by a 2-cycle), two independent edges may cross arbitrarily many times in a star-simple drawing. We consider star-simple drawings of $K_n$ with no empty lens. In this setting we prove an upper bound of $3((n-4)!)$ on the maximum number of crossings between any pair of edges. It follows that the total number of crossings is finite and upper bounded by $n!$.

preprint2020arXiv

Extending Partial Orthogonal Drawings

We study the planar orthogonal drawing style within the framework of partial representation extension. Let $(G,H,Γ_H )$ be a partial orthogonal drawing, i.e., G is a graph, $H\subseteq G$ is a subgraph and $Γ_H$ is a planar orthogonal drawing of H. We show that the existence of an orthogonal drawing $Γ_G$ of $G$ that extends $Γ_H$ can be tested in linear time. If such a drawing exists, then there also is one that uses $O(|V(H)|)$ bends per edge. On the other hand, we show that it is NP-complete to find an extension that minimizes the number of bends or has a fixed number of bends per edge.

preprint2020arXiv

A Topological Similarity Measure between Multi-Field Data using Multi-Resolution Reeb Spaces

Searching topological similarity between a pair of shapes or data is an important problem in data analysis and visualization. The problem of computing similarity measures using scalar topology has been studied extensively and proven useful in shape and data matching. Even though multi-field (or multivariate) topology-based techniques reveal richer topological features, research on computing similarity measures using multi-field topology is still in its infancy. In the current paper, we propose a novel similarity measure between two piecewise-linear multi-fields based on their multi-resolution Reeb spaces - a newly developed data-structure that captures the topology of a multi-field. Overall, our method consists of two steps: (i) building a multi-resolution Reeb space corresponding to each of the multi-fields and (ii) proposing a similarity measure for a list of matching pairs (of nodes), obtained by comparing the multi-resolution Reeb spaces. We demonstrate an application of the proposed similarity measure by detecting the nuclear scission point in a time-varying multi-field data from computational physics.

preprint2020arXiv

Space-Aware Reconfiguration

We consider the problem of reconfiguring a set of physical objects into a desired target configuration, a typical (sub)task in robotics and automation, arising in product assembly, packaging, stocking store shelves, and more. In this paper we address a variant, which we call space-aware reconfiguration, where the goal is to minimize the physical space needed for the reconfiguration, while obeying constraints on the allowable collision-free motions of the objects. Since for given start and target configurations, reconfiguration may be impossible, we translate the entire target configuration rigidly into a location that admits a valid sequence of moves, where each object moves in turn just once, along a straight line, from its starting to its target location, so that the overall physical space required by the start, all intermediate, and target configurations for all the objects is minimized. We investigate two variants of space-aware reconfiguration for the often examined setting of $n$ unit discs in the plane, depending on whether the discs are distinguishable (labeled) or indistinguishable (unlabeled). For the labeled case, we propose a representation of size $O(n^4)$ of the space

preprint2020arXiv

SPARE3D: A Dataset for SPAtial REasoning on Three-View Line Drawings

Spatial reasoning is an important component of human intelligence. We can imagine the shapes of 3D objects and reason about their spatial relations by merely looking at their three-view line drawings in 2D, with different levels of competence. Can deep networks be trained to perform spatial reasoning tasks? How can we measure their "spatial intelligence"? To answer these questions, we present the SPARE3D dataset. Based on cognitive science and psychometrics, SPARE3D contains three types of 2D-3D reasoning tasks on view consistency, camera pose, and shape generation, with increasing difficulty. We then design a method to automatically generate a large number of challenging questions with ground truth answers for each task. They are used to provide supervision for training our baseline models using state-of-the-art architectures like ResNet. Our experiments show that although convolutional networks have achieved superhuman performance in many visual learning tasks, their spatial reasoning performance on SPARE3D tasks is either lower than average human performance or even close to random guesses. We hope SPARE3D can stimulate new problem formulations and network designs for sp

preprint2020arXiv

Counting the Number of Crossings in Geometric Graphs

A geometric graph is a graph whose vertices are points in general position in the plane and its edges are straight line segments joining these points. In this paper we give an $O(n^2 \log n)$ algorithm to compute the number of pairs of edges that cross in a geometric graph on $n$ points. For layered, and convex geometric graphs the algorithm takes $O(n^2)$ time.

preprint2020arXiv

Isotopic Arrangement of Simple Curves: an Exact Numerical Approach based on Subdivision

This paper presents the first purely numerical (i.e., non-algebraic) subdivision algorithm for the isotopic approximation of a simple arrangement of curves. The arrangement is "simple" in the sense that any three curves have no common intersection, any two curves intersect transversally, and each curve is non-singular. A curve is given as the zero set of an analytic function $f:\mathbb{R}^2\rightarrow \mathbb{R}^2$, and effective interval forms of $f, \frac{\partial{f}}{\partial{x}}, \frac{\partial{f}}{\partial{y}}$ are available. Our solution generalizes the isotopic curve approximation algorithms of Plantinga-Vegter (2004) and Lin-Yap (2009). We use certified numerical primitives based on interval methods. Such algorithms have many favorable properties: they are practical, easy to implement, suffer no implementation gaps, integrate topological with geometric computation, and have adaptive as well as local complexity. A version of this paper without the appendices appeared in Lien et al. (2014).

preprint2020arXiv

Automatic feature-preserving size field for 3D mesh generation

This paper presents a methodology aiming at easing considerably the generation of high-quality meshes for complex 3D domains. We show that the whole mesh generation process can be controlled with only five parameters to generate in one stroke quality meshes for arbitrary geometries. The main idea is to build a meshsize field $h(x)$ taking local features of the geometry, such as curvatures, into account. Meshsize information is then propagated from the surfaces into the volume, ensuring that the magnitude of $\vert \nabla h \vert$ is always controlled so as to obtain a smoothly graded mesh. As the meshsize field is stored in an independent octree data structure, the function h can be computed separately, and then plugged in into any mesh generator able to respect a prescribed meshsize field. The whole procedure is automatic, in the sense that minimal interaction with the user is required. Applications examples based on models taken from the very large ABC dataset, are then presented, all treated with the same generic set of parameter values, to demonstrate the efficiency and the universality of the technique.

preprint2020arXiv

TopoMap: A 0-dimensional Homology Preserving Projection of High-Dimensional Data

Multidimensional Projection is a fundamental tool for high-dimensional data analytics and visualization. With very few exceptions, projection techniques are designed to map data from a high-dimensional space to a visual space so as to preserve some dissimilarity (similarity) measure, such as the Euclidean distance for example. In fact, although adopting distinct mathematical formulations designed to favor different aspects of the data, most multidimensional projection methods strive to preserve dissimilarity measures that encapsulate geometric properties such as distances or the proximity relation between data objects. However, geometric relations are not the only interesting property to be preserved in a projection. For instance, the analysis of particular structures such as clusters and outliers could be more reliably performed if the mapping process gives some guarantee as to topological invariants such as connected components and loops. This paper introduces TopoMap, a novel projection technique which provides topological guarantees during the mapping process. In particular, the proposed method performs the mapping from a high-dimensional space to a visual space, while preservi