### Top 5 Arxiv Papers Today in Computational Geometry

##### #1. Volumetric Untrimming: Precise decomposition of trimmed trivariates into tensor products
###### Fady Massarwi, Pablo Antolin, Gershon Elber
3D objects, modeled using Computer Aided Geometric Design tools, are traditionally represented using a boundary representation (B-rep), and typically use spline functions to parameterize these boundary surfaces. However, recent development in physical analysis, in isogeometric analysis (IGA) in specific, necessitates a volumetric parametrization of the interior of the object. IGA is performed directly by integrating over the spline spaces of the volumetric spline representation of the object. Typically, tensor-product B-spline trivariates are used to parameterize the volumetric domain. A general 3D object, that can be modeled in contemporary B-rep CAD tools, is typically represented using trimmed B-spline surfaces. In order to capture the generality of the contemporary B-rep modeling space, while supporting IGA needs, Massarwi and Elber (2016) proposed the use of trimmed trivariates volumetric elements. However, the use of trimmed geometry makes the integration process more difficult since integration over trimmed B-spline basis...
more | pdf | html
###### Tweets ComputerPapers: Volumetric Untrimming: Precise decomposition of trimmed trivariates into tensor products. https://t.co/28cGm4Ej6V
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 9984
Unqiue Words: 2407

##### #2. Drawing planar graphs with few segments on a polynomial grid
###### Philipp Kindermann, Tamara Mchedlidze, Thomas Schneck, Antonios Symvonis
The visual complexity of a plane graph drawing is defined to be the number of basic geometric objects needed to represent all its edges. In particular, one object may represent multiple edges (e.g., one needs only one line segment to draw a path with an arbitrary number of edges). A crossing-free straight-line drawing of a graph is called monotone if there is a monotone path between any pair of vertices with respect to some direction. We study drawings of trees, outerplanar graphs, and general planar graphs with few segments on a polynomial size grid. For trees, the grid size is $n\times n$. For 3-connected planar graphs and biconnected outerplanar graphs, we compute such drawings that are also monotone.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 9713
Unqiue Words: 1863

##### #3. Topological Data Analysis in Information Space
###### Herbert Edelsbrunner, Ziga Virk, Hubert Wagner
Various kinds of data are routinely represented as discrete probability distributions. Examples include text documents summarized by histograms of word occurrences and images represented as histograms of oriented gradients. Viewing a discrete probability distribution as a point in the standard simplex of the appropriate dimension, we can understand collections of such objects in geometric and topological terms. Importantly, instead of using the standard Euclidean distance, we look into dissimilarity measures with information-theoretic justification, and we develop the theory needed for applying topological data analysis in this setting. In doing so, we emphasize constructions that enable usage of existing computational topology software in this context.
more | pdf | html
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 3
Total Words: 11021
Unqiue Words: 2630

##### #4. Preprocessing Ambiguous Imprecise Points
###### Ivor van der Hoog, Irina Kostitsyna, Maarten Löffler, Bettina Speckmann
Let ${R} = \{R_1, R_2, ..., R_n\}$ be a set of regions and let $X = \{x_1, x_2, ..., x_n\}$ be an (unknown) point set with $x_i \in R_i$. Region $R_i$ represents the uncertainty region of $x_i$. We consider the following question: how fast can we establish order if we are allowed to preprocess the regions in $R$? The preprocessing model of uncertainty uses two consecutive phases: a preprocessing phase which has access only to ${R}$ followed by a reconstruction phase during which a desired structure on $X$ is computed. Recent results in this model parametrize the reconstruction time by the ply of ${R}$, which is the maximum overlap between the regions in ${R}$. We introduce the ambiguity $A({R})$ as a more fine-grained measure of the degree of overlap in ${R}$. We show how to preprocess a set of $d$-dimensional disks in $O(n \log n)$ time such that we can sort $X$ (if $d=1$) and reconstruct a quadtree on $X$ (if $d\geq 1$ but constant) in $O(A({R}))$ time. If $A({R})$ is sub-linear, then reporting the result dominates the running...
more | pdf | html
None.
###### Tweets ComputerPapers: Preprocessing Ambiguous Imprecise Points. https://t.co/nbeySRMXNC
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 11149
Unqiue Words: 2128

##### #5. Dynamic Geometric Data Structures via Shallow Cuttings
###### Timothy M. Chan
We present new results on a number of fundamental problems about dynamic geometric data structures: 1. We describe the first fully dynamic data structures with sublinear amortized update time for maintaining (i) the number of vertices or the volume of the convex hull of a 3D point set, (ii) the largest empty circle for a 2D point set, (iii) the Hausdorff distance between two 2D point sets, (iv) the discrete 1-center of a 2D point set, (v)the number of maximal (i.e., skyline) points in a 3D point set. The update times are near $n^{11/12}$ for (i) and (ii), $n^{7/8}$ for (iii) and (iv), and $n^{2/3}$ for (v). Previously, sublinear bounds were known only for restricted `semi-online' settings [Chan, SODA 2002]. 2. We slightly improve previous fully dynamic data structures for answering extreme point queries for the convex hull of a 3D point set and nearest neighbor search for a 2D point set. The query time is $O(\log^2n)$, and the amortized update time is $O(\log^4n)$ instead of $O(\log^5n)$ [Chan, SODA 2006; Kaplan et al., SODA...
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 8322
Unqiue Words: 1827

Assert is a website where the best academic papers on arXiv (computer science, math, physics), bioRxiv (biology), BITSS (reproducibility), EarthArXiv (earth science), engrXiv (engineering), LawArXiv (law), PsyArXiv (psychology), SocArXiv (social science), and SportRxiv (sport research) bubble to the top each day.

Papers are scored (in real-time) based on how verifiable they are (as determined by their Github repos) and how interesting they are (based on Twitter).

To see top papers, follow us on twitter @assertpub_ (arXiv), @assert_pub (bioRxiv), and @assertpub_dev (everything else).

To see beautiful figures extracted from papers, follow us on Instagram.

Tracking 99,586 papers.

###### Search
Sort results based on if they are interesting or reproducible.
Interesting
Reproducible
Online
###### Stats
Tracking 99,586 papers.