Top 10 Arxiv Papers Today in Computational Geometry


2.004 Mikeys
#1. The EdgeConflict Predicate in the 3D Apollonius Diagram
Manos N. Kamarianakis
In this paper we study one of the fundamental predicates required for the construction of the 3D Apollonius diagram (also known as the 3D Additively Weighted Voronoi diagram), namely the EdgeConflict predicate: given five sites $S_i, S_j,S_k,S_l,S_m$ that define an edge $e_{ijklm}$ in the 3D Apollonius diagram, and a sixth query site $S_q$, the predicate determines the portion of $e_{ijklm}$ that will disappear in the Apollonius diagram of the six sites due to the insertion of $S_q$. Our focus is on the algorithmic analysis of the predicate with the aim to minimize its algebraic degree. We decompose the main predicate into three sub-predicates, which are then evaluated with the aid of four additional primitive operations. We show that the maximum algebraic degree required to answer any of the sub-predicates and primitives, and, thus, our main predicate is 10. Among the tools we use is the 3D inversion transformation. In the scope of this paper and due to space limitations, only non-degenerate configurations are considered,...
more | pdf | html
Figures
Tweets
ComputerPapers: The EdgeConflict Predicate in the 3D Apollonius Diagram. https://t.co/7Gz31nMiUY
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 25222
Unqiue Words: 3125

2.004 Mikeys
#2. Maximum-Width Empty Square and Rectangular Annulus
Sang Won Bae, Arpita Baral, Priya Ranjan Sinha Mahapatra
An annulus is, informally, a ring-shaped region, often described by two concentric circles. The maximum-width empty annulus problem asks to find an annulus of a certain shape with the maximum possible width that avoids a given set of $n$ points in the plane. This problem can also be interpreted as the problem of finding an optimal location of a ring-shaped obnoxious facility among the input points. In this paper, we study square and rectangular variants of the maximum-width empty anuulus problem, and present first nontrivial algorithms. Specifically, our algorithms run in $O(n^3)$ and $O(n^2 \log n)$ time for computing a maximum-width empty axis-parallel square and rectangular annulus, respectively. Both algorithms use only $O(n)$ space.
more | pdf | html
Figures
None.
Tweets
ComputerPapers: Maximum-Width Empty Square and Rectangular Annulus. https://t.co/jQdGoG4qiA
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 8894
Unqiue Words: 1646

2.0 Mikeys
#3. 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

1.995 Mikeys
#4. An Efficient Combinatorial Algorithm for Optimal Compression of a Polyline with Segments and Arcs
Alexander Gribov
The task of finding the optimal compression of a polyline with straight-line segments and arcs is performed in many applications, such as polyline compression, noise filtering, and feature recognition. Optimal compression algorithms find the best solution using the dynamic programming approach, which requires a significant amount of arc fitting. This paper describes an improvement to the dynamic programming approach by reducing the amount of arc fitting necessary to find the optimal solution. Instead of processing from the second to the last vertices in the dynamic programming approach, the algorithm proceeds forward and skips as many steps as possible without affecting the inference in any way. Such a modification extends the practical application of the algorithm to polylines having arcs with a large number of vertices.
more | pdf | html
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 3006
Unqiue Words: 834

0.0 Mikeys
#5. Perception of Symmetries in Drawings of Graphs
Felice De Luca, Stephen Kobourov, Helen Purchase
Symmetry is an important factor in human perception in general, as well as in the visualization of graphs in particular. There are three main types of symmetry: reflective, translational, and rotational. We report the results of a human subjects experiment to determine what types of symmetries are more salient in drawings of graphs. We found statistically significant evidence that vertical reflective symmetry is the most dominant (when selecting among vertical reflective, horizontal reflective, and translational). We also found statistically significant evidence that rotational symmetry is affected by the number of radial axes (the more, the better), with a notable exception at four axes.
more | pdf | html
Figures
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 5900
Unqiue Words: 1910

0.0 Mikeys
#6. The Parameterized Complexity of Finding Point Sets with Hereditary Properties
David Eppstein, Daniel Lokshtanov
We consider problems where the input is a set of points in the plane and an integer $k$, and the task is to find a subset $S$ of the input points of size $k$ such that $S$ satisfies some property. We focus on properties that depend only on the order type of the points and are monotone under point removals. We show that not all such problems are fixed-parameter tractable parameterized by $k$, by exhibiting a property defined by three forbidden patterns for which finding a $k$-point subset with the property is $\mathrm{W}[1]$-complete and (assuming the exponential time hypothesis) cannot be solved in time $n^{o(k/\log k)}$. However, we show that problems of this type are fixed-parameter tractable for all properties that include all collinear point sets, properties that exclude at least one convex polygon, and properties defined by a single forbidden pattern.
more | pdf | html
Figures
None.
Tweets
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 2
Total Words: 9087
Unqiue Words: 1815

0.0 Mikeys
#7. 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
#8. Algorithms for metric learning via contrastive embeddings
Diego Ihara Centurion, Neshat Mohammadi, Anastasios Sidiropoulos
We study the problem of supervised learning a metric space under discriminative constraints. Given a universe $X$ and sets ${\cal S}, {\cal D}\subset {X \choose 2}$ of similar and dissimilar pairs, we seek to find a mapping $f:X\to Y$, into some target metric space $M=(Y,\rho)$, such that similar objects are mapped to points at distance at most $u$, and dissimilar objects are mapped to points at distance at least $\ell$. More generally, the goal is to find a mapping of maximum accuracy (that is, fraction of correctly classified pairs). We propose approximation algorithms for various versions of this problem, for the cases of Euclidean and tree metric spaces. For both of these target spaces, we obtain fully polynomial-time approximation schemes (FPTAS) for the case of perfect information. In the presence of imperfect information we present approximation algorithms that run in quasipolynomial time (QPTAS). Our algorithms use a combination of tools from metric embeddings and graph partitioning, that could be of independent interest.
more | pdf | html
Figures
Tweets
nmfeeds: [O] https://t.co/PMn3FaByUj Algorithms for metric learning via contrastive embeddings. We study the problem of supervised ...
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 3
Total Words: 13679
Unqiue Words: 2438

0.0 Mikeys
#9. Colored range closest-pair problem under general distance functions
Jie Xue
The range closest-pair (RCP) problem is the range-search version of the classical closest-pair problem, which aims to store a given dataset of points in some data structure such that when a query range $X$ is specified, the closest pair of points contained in $X$ can be reported efficiently. A natural generalization of the RCP problem is the {colored range closest-pair} (CRCP) problem in which the given data points are colored and the goal is to find the closest {bichromatic} pair contained in the query range. All the previous work on the RCP problem was restricted to the uncolored version and the Euclidean distance function. In this paper, we make the first progress on the CRCP problem. We investigate the problem under a general distance function induced by a monotone norm; in particular, this covers all the $L_p$-metrics for $p > 0$ and the $L_\infty$-metric. We design efficient $(1+\varepsilon)$-approximate CRCP data structures for orthogonal queries in $\mathbb{R}^2$, where $\varepsilon>0$ is a pre-specified parameter. The...
more | pdf | html
Figures
None.
Tweets
ComputerPapers: Colored range closest-pair problem under general distance functions. https://t.co/286vzsfMNI
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 17961
Unqiue Words: 2405

0.0 Mikeys
#10. On tail estimates for Randomized Incremental Construction
Sandeep Sen
By combining several interesting applications of random sampling in geometric algorithms like point location, linear programming, segment intersections, binary space partitioning, Clarkson and Shor \cite{CS89} developed a general framework of randomized incremental construction (RIC ). The basic idea is to add objects in a random order and show that this approach yields efficient/optimal bounds on {\bf expected} running time. Even quicksort can be viewed as a special case of this paradigm. However, unlike quicksort, for most of these problems, attempts to obtain sharper tail estimates on the running time had proved inconclusive. Barring some results by \cite{MSW93,CMS92,Seidel91a}, the general question remains unresolved. In this paper we present some general techniques to obtain tail estimates for RIC and and provide applications to some fundamental problems like Delaunay triangulations and construction of Visibility maps of intersecting line segments. The main result of the paper centers around a new and careful application...
more | pdf | html
Figures
None.
Tweets
ComputerPapers: On tail estimates for Randomized Incremental Construction. https://t.co/BrX9ClOqS7
Github
None.
Youtube
None.
Other stats
Sample Sizes : None.
Authors: 1
Total Words: 8730
Unqiue Words: 2021

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 57,756 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 57,756 papers.