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
ComputerPapers:
The EdgeConflict Predicate in the 3D Apollonius Diagram. https://t.co/7Gz31nMiUY

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 25222

Unqiue Words: 3125

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
None.

ComputerPapers:
Maximum-Width Empty Square and Rectangular Annulus. https://t.co/jQdGoG4qiA

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 8894

Unqiue Words: 1646

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.

ComputerPapers:
Computing the Minkowski Sum of Convex Polytopes in $\Re^d$. https://t.co/FTfsQlVAe4

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 5768

Unqiue Words: 1166

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
None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 3006

Unqiue Words: 834

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
None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 5900

Unqiue Words: 1910

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
None.

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 9087

Unqiue Words: 1815

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.

ComputerPapers:
Searching for the closest-pair in a query translate. https://t.co/mwRBKqvnUD

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 20441

Unqiue Words: 2471

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
nmfeeds:
[O] https://t.co/PMn3FaByUj Algorithms for metric learning via contrastive embeddings. We study the problem of supervised ...

None.

None.

Sample Sizes : None.

Authors: 3

Total Words: 13679

Unqiue Words: 2438

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
None.

ComputerPapers:
Colored range closest-pair problem under general distance functions. https://t.co/286vzsfMNI

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 17961

Unqiue Words: 2405

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
None.

ComputerPapers:
On tail estimates for Randomized Incremental Construction. https://t.co/BrX9ClOqS7

None.

None.

Sample Sizes : None.

Authors: 1

Total Words: 8730

Unqiue Words: 2021

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.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible