### Top 10 Arxiv Papers Today in Computational Geometry

##### #1. Computing the Minkowski Sum of Convex Polytopes in $\Re^d$
###### Sandip Das, Swami Sarvottamananda
We propose a method to efficiently compute the Minkowski sum, denoted by binary operator $\oplus$ in the paper, of convex polytopes in $\Re^d$ using their face lattice structures as input. In plane, the Minkowski sum of convex polygons can be computed in linear time of the total number of vertices of the polygons. In $\Re^d$, we first show how to compute the Minkowski sum, $P \oplus Q$, of two convex polytopes $P$ and $Q$ of input size $n$ and $m$ respectively in time $O(nm)$. Then we generalize the method to compute the Minkowski sum of $n$ convex polytopes, $P_1 \oplus P_2 \oplus \cdots \oplus P_n$, in $\Re^d$ in time $O(\prod_{i}^{n}N_i)$, where $P_1$, $P_2$, $\dots$, $P_n$ are $n$ input convex polytopes and for each $i$, $N_i$ is size of the face lattice structure of $P_i$. Our algorithm for Minkowski sum of two convex polytopes is optimal in the worst case since the output face lattice structure of $P\oplus Q$ for convex polytopes in $\Re^d$ can be $O(nm)$ in worst case.
more | pdf | html
None.
###### Tweets
ComputerPapers: Computing the Minkowski Sum of Convex Polytopes in $\Re^d$. https://t.co/FTfsQlVAe4
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 5768
Unqiue Words: 1166

##### #2. A 36-Element Solution To Schneiders' Pyramid Hex-Meshing Problem And A Parity-Changing Template For Hex-Mesh Revision
###### Shang Xiang, Jianfei Liu
In this paper, we present a solution that uses the least number of hexahedra to build a pyramid, which is the key block required for one type of automatic hex-meshing method to be successful. When the initial result of a hex-meshing program is not appropriate for specific applications, some templates are used for revision. The templates reported thus far are parity-preserving, which means that the parity of the number of hexahedra in a mesh is unchanged after a revision following the templates. We present a parity-changing template that makes the template set integral and more effective. These two findings are obtained by a program that we developed for this study, which is a tool for researchers to observe the characteristics of small hexahedral packings.
more | pdf | html
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 3323
Unqiue Words: 1107

##### #3. Searching for the closest-pair in a query translate
###### Jie Xue, Yuan Li, Saladi Rahul, Ravi Janardan
In this paper, we consider a range-search variant of the closest-pair problem. Let $\varGamma$ be a fixed shape in the plane. We are interested in storing a given set of plane points in some data structure such that for any specified translate of $\varGamma$, the closest pair of points contained in the translate can be reported efficiently. We present results on this problem for two important cases: when $\varGamma$ is a polygon (possibly with holes) and when $\varGamma$ is a general convex body whose boundary is smooth. When $\varGamma$ is a polygon, we present a data structure using $O(n)$ space and $O(\log n)$ query time, which is asymptotically optimal. When $\varGamma$ is a general convex body with a smooth boundary, we give a near-optimal data structure using $O(n \log n)$ space and $O(\log^2 n)$ query time. Our results settle some open questions posed by Xue et al. [SoCG 2018].
more | pdf | html
None.
###### Tweets
ComputerPapers: Searching for the closest-pair in a query translate. https://t.co/mwRBKqvnUD
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 20441
Unqiue Words: 2471

##### #4. Geodesic farthest-point Voronoi diagram in linear time
###### Luis Barba
Let $P$ be a simple polygon with $n$ vertices. For any two points in $P$, the geodesic distance between them is the length of the shortest path that connects them among all paths contained in $P$. Given a set $S$ of $m$ sites being a subset of the vertices of $P$, we present a randomized algorithm to compute the geodesic farthest-point Voronoi diagram of $S$ in $P$ running in expected $O(n + m)$ time. That is, a partition of $P$ 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 distance. In particular, this algorithm can be extended to run in expected $O(n + m\log m)$ time when $S$ is an arbitrary set of $m$ sites contained in $P$, thereby solving the open problem posed by Mitchell in Chapter 27 of the Handbook of Computational Geometry.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 1
Total Words: 12585
Unqiue Words: 1892

##### #5. A Unified Framework for Clustering Constrained Data without Locality Property
###### Hu Ding, Jinhui Xu
In this paper, we consider a class of constrained clustering problems of points in $\mathbb{R}^{d}$, where $d$ could be rather high. A common feature of these problems is that their optimal clusterings no longer have the locality property (due to the additional constraints), which is a key property required by many algorithms for their unconstrained counterparts. To overcome the difficulty caused by the loss of locality, we present in this paper a unified framework, called {\em Peeling-and-Enclosing (PnE)}, to iteratively solve two variants of the constrained clustering problems, {\em constrained $k$-means clustering} ($k$-CMeans) and {\em constrained $k$-median clustering} ($k$-CMedian). Our framework is based on two standalone geometric techniques, called {\em Simplex Lemma} and {\em Weaker Simplex Lemma}, for $k$-CMeans and $k$-CMedian, respectively. The simplex lemma (or weaker simplex lemma) enables us to efficiently approximate the mean (or median) point of an unknown set of points by searching a small-size grid, independent...
more | pdf | html
None.
###### Tweets
Memoirs: A Unified Framework for Clustering Constrained Data without Locality Property. https://t.co/u40fxnwQFN
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 21122
Unqiue Words: 3463

##### #6. An ETH-Tight Exact Algorithm for Euclidean TSP
###### Mark de Berg, Hans L. Bodlaender, Sandor Kisfaludi-Bak, Sudeshna Kolay
We study exact algorithms for {\sc Euclidean TSP} in $\mathbb{R}^d$. In the early 1990s algorithms with $n^{O(\sqrt{n})}$ running time were presented for the planar case, and some years later an algorithm with $n^{O(n^{1-1/d})}$ running time was presented for any $d\geq 2$. Despite significant interest in subexponential exact algorithms over the past decade, there has been no progress on {\sc Euclidean TSP}, except for a lower bound stating that the problem admits no $2^{O(n^{1-1/d-\epsilon})}$ algorithm unless ETH fails. Up to constant factors in the exponent, we settle the complexity of {\sc Euclidean TSP} by giving a $2^{O(n^{1-1/d})}$ algorithm and by showing that an $2^{o(n^{1-1/d})}$ algorithm does not exist unless ETH fails.
more | pdf | html
None.
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 4
Total Words: 10099
Unqiue Words: 2056

##### #7. Dihedral Rigidity and Deformation
###### Nina Amenta, Carlos Rojas
We consider defining the embedding of a triangle mesh into $R^3$, up to translation, rotation, and scale, by its vector of dihedral angles. Theoretically, we show that locally, almost everywhere, the map from realizable vectors of dihedrals to mesh embeddings is one-to-one. We experiment with a heuristic method for mapping straight-line interpolations in dihedral space to interpolations between mesh embeddings and produce smooth and intuitively appealing morphs between three-dimensional shapes.
more | pdf | html
###### Tweets
ComputerPapers: Dihedral Rigidity and Deformation. https://t.co/jEalgiUU9a
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 4961
Unqiue Words: 1637

##### #8. Approximate Minimum-Weight Matching with Outliers under Translation
###### Pankaj K. Agarwal, Haim Kaplan, Geva Kipper, Wolfgang Mulzer, Günter Rote, Micha Sharir, Allen Xiao
Our goal is to compare two planar point sets by finding subsets of a given size such that a minimum-weight matching between them has the smallest weight. This can be done by a translation of one set that minimizes the weight of the matching. We give efficient algorithms (a) for finding approximately optimal matchings, when the cost of a matching is the $L_p$-norm of the tuple of the Euclidean distances between the pairs of matched points, for any $p\in [1,\infty]$, and (b)~for constructing small-size approximate minimization (or matching) diagrams: partitions of the translation space into regions, together with an approximate optimal matching for each region.
more | pdf | html
None.
###### Tweets
ComputerPapers: Approximate Minimum-Weight Matching with Outliers under Translation. https://t.co/W3G6PjbfiB
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 7
Total Words: 7883
Unqiue Words: 1774

##### #9. Extending the centerpoint theorem to multiple points
###### Alexander Pilz, Patrick Schnider
The centerpoint theorem is a well-known and widely used result in discrete geometry. It states that for any point set $P$ of $n$ points in $\mathbb{R}^d$, there is a point $c$, not necessarily from $P$, such that each halfspace containing $c$ contains at least $\frac{n}{d+1}$ points of $P$. Such a point $c$ is called a centerpoint, and it can be viewed as a generalization of a median to higher dimensions. In other words, a centerpoint can be interpreted as a good representative for the point set $P$. But what if we allow more than one representative? For example in one-dimensional data sets, often certain quantiles are chosen as representatives instead of the median. We present a possible extension of the concept of quantiles to higher dimensions. The idea is to find a set $Q$ of (few) points such that every halfspace that contains one point of $Q$ contains a large fraction of the points of $P$ and every halfspace that contains more of $Q$ contains an even larger fraction of $P$. This setting is comparable to the well-studied...
more | pdf | html
None.
###### Tweets
ComputerPapers: Extending the centerpoint theorem to multiple points. https://t.co/Bd0AwL84aD
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8928
Unqiue Words: 1670

##### #10. Polyline Drawings with Topological Constraints
###### Emilio Di Giacomo, Peter Eades, Giuseppe Liotta, Henk Meijer, Fabrizio Montecchiani
Let $G$ be a simple topological graph and let $\Gamma$ be a polyline drawing of $G$. We say that $\Gamma$ \emph{partially preserves the topology} of $G$ if it has the same external boundary, the same rotation system, and the same set of crossings as $G$. Drawing $\Gamma$ fully preserves the topology of $G$ if the planarization of $G$ and the planarization of $\Gamma$ have the same planar embedding. We show that if the set of crossing-free edges of $G$ forms a connected spanning subgraph, then $G$ admits a polyline drawing that partially preserves its topology and that has curve complexity at most three (i.e., at most three bends per edge). If, however, the set of crossing-free edges of $G$ is not a connected spanning subgraph, the curve complexity may be $\Omega(\sqrt{n})$. Concerning drawings that fully preserve the topology, we show that if $G$ has skewness $k$, it admits one such drawing with curve complexity at most $2k$; for skewness-1 graphs, the curve complexity can be reduced to one, which is a tight bound. We also...
more | pdf | html
None.
###### Tweets
ComputerPapers: Polyline Drawings with Topological Constraints. https://t.co/bRt9P2T4JB
None.
None.
###### Other stats
Sample Sizes : None.
Authors: 5
Total Words: 10781
Unqiue Words: 1658

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 72,893 papers.

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