Top 10 Arxiv Papers Today in Computational Geometry


0.0 Mikeys
#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
Figures
None.
Tweets
ComputerPapers: Computing the Minkowski Sum of Convex Polytopes in $\Re^d$. https://t.co/FTfsQlVAe4
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 5768
Unqiue Words: 1166

0.0 Mikeys
#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
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 3323
Unqiue Words: 1107

0.0 Mikeys
#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
Figures
None.
Tweets
ComputerPapers: Searching for the closest-pair in a query translate. https://t.co/mwRBKqvnUD
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 20441
Unqiue Words: 2471

0.0 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 12585
Unqiue Words: 1892

0.0 Mikeys
#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
Figures
None.
Tweets
Memoirs: A Unified Framework for Clustering Constrained Data without Locality Property. https://t.co/u40fxnwQFN
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 21122
Unqiue Words: 3463

0.0 Mikeys
#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
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 4
Total Words: 10099
Unqiue Words: 2056

0.0 Mikeys
#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
Figures
Tweets
ComputerPapers: Dihedral Rigidity and Deformation. https://t.co/jEalgiUU9a
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 4961
Unqiue Words: 1637

0.0 Mikeys
#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
Figures
None.
Tweets
ComputerPapers: Approximate Minimum-Weight Matching with Outliers under Translation. https://t.co/W3G6PjbfiB
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 7
Total Words: 7883
Unqiue Words: 1774

0.0 Mikeys
#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
Figures
None.
Tweets
ComputerPapers: Extending the centerpoint theorem to multiple points. https://t.co/Bd0AwL84aD
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 8928
Unqiue Words: 1670

0.0 Mikeys
#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
Figures
None.
Tweets
ComputerPapers: Polyline Drawings with Topological Constraints. https://t.co/bRt9P2T4JB
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 5
Total Words: 10781
Unqiue Words: 1658

About

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
Categories
All
Astrophysics
Cosmology and Nongalactic Astrophysics
Earth and Planetary Astrophysics
Astrophysics of Galaxies
High Energy Astrophysical Phenomena
Instrumentation and Methods for Astrophysics
Solar and Stellar Astrophysics
Condensed Matter
Disordered Systems and Neural Networks
Mesoscale and Nanoscale Physics
Materials Science
Other Condensed Matter
Quantum Gases
Soft Condensed Matter
Statistical Mechanics
Strongly Correlated Electrons
Superconductivity
Computer Science
Artificial Intelligence
Hardware Architecture
Computational Complexity
Computational Engineering, Finance, and Science
Computational Geometry
Computation and Language
Cryptography and Security
Computer Vision and Pattern Recognition
Computers and Society
Databases
Distributed, Parallel, and Cluster Computing
Digital Libraries
Discrete Mathematics
Data Structures and Algorithms
Emerging Technologies
Formal Languages and Automata Theory
General Literature
Graphics
Computer Science and Game Theory
Human-Computer Interaction
Information Retrieval
Information Theory
Machine Learning
Logic in Computer Science
Multiagent Systems
Multimedia
Mathematical Software
Numerical Analysis
Neural and Evolutionary Computing
Networking and Internet Architecture
Other Computer Science
Operating Systems
Performance
Programming Languages
Robotics
Symbolic Computation
Sound
Software Engineering
Social and Information Networks
Systems and Control
Economics
Econometrics
General Economics
Theoretical Economics
Electrical Engineering and Systems Science
Audio and Speech Processing
Image and Video Processing
Signal Processing
General Relativity and Quantum Cosmology
General Relativity and Quantum Cosmology
High Energy Physics - Experiment
High Energy Physics - Experiment
High Energy Physics - Lattice
High Energy Physics - Lattice
High Energy Physics - Phenomenology
High Energy Physics - Phenomenology
High Energy Physics - Theory
High Energy Physics - Theory
Mathematics
Commutative Algebra
Algebraic Geometry
Analysis of PDEs
Algebraic Topology
Classical Analysis and ODEs
Combinatorics
Category Theory
Complex Variables
Differential Geometry
Dynamical Systems
Functional Analysis
General Mathematics
General Topology
Group Theory
Geometric Topology
History and Overview
Information Theory
K-Theory and Homology
Logic
Metric Geometry
Mathematical Physics
Numerical Analysis
Number Theory
Operator Algebras
Optimization and Control
Probability
Quantum Algebra
Rings and Algebras
Representation Theory
Symplectic Geometry
Spectral Theory
Statistics Theory
Mathematical Physics
Mathematical Physics
Nonlinear Sciences
Adaptation and Self-Organizing Systems
Chaotic Dynamics
Cellular Automata and Lattice Gases
Pattern Formation and Solitons
Exactly Solvable and Integrable Systems
Nuclear Experiment
Nuclear Experiment
Nuclear Theory
Nuclear Theory
Physics
Accelerator Physics
Atmospheric and Oceanic Physics
Applied Physics
Atomic and Molecular Clusters
Atomic Physics
Biological Physics
Chemical Physics
Classical Physics
Computational Physics
Data Analysis, Statistics and Probability
Physics Education
Fluid Dynamics
General Physics
Geophysics
History and Philosophy of Physics
Instrumentation and Detectors
Medical Physics
Optics
Plasma Physics
Popular Physics
Physics and Society
Space Physics
Quantitative Biology
Biomolecules
Cell Behavior
Genomics
Molecular Networks
Neurons and Cognition
Other Quantitative Biology
Populations and Evolution
Quantitative Methods
Subcellular Processes
Tissues and Organs
Quantitative Finance
Computational Finance
Economics
General Finance
Mathematical Finance
Portfolio Management
Pricing of Securities
Risk Management
Statistical Finance
Trading and Market Microstructure
Quantum Physics
Quantum Physics
Statistics
Applications
Computation
Methodology
Machine Learning
Other Statistics
Statistics Theory
Feedback
Online
Stats
Tracking 72,893 papers.