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

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.

Sample Sizes : None.

Authors: 2

Total Words: 3323

Unqiue Words: 1107

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

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.

Sample Sizes : None.

Authors: 1

Total Words: 12585

Unqiue Words: 1892

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.

Memoirs:
A Unified Framework for Clustering Constrained Data without Locality Property. https://t.co/u40fxnwQFN

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 21122

Unqiue Words: 3463

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.

Sample Sizes : None.

Authors: 4

Total Words: 10099

Unqiue Words: 2056

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
ComputerPapers:
Dihedral Rigidity and Deformation. https://t.co/jEalgiUU9a

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 4961

Unqiue Words: 1637

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.

ComputerPapers:
Approximate Minimum-Weight Matching with Outliers under Translation. https://t.co/W3G6PjbfiB

None.

None.

Sample Sizes : None.

Authors: 7

Total Words: 7883

Unqiue Words: 1774

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.

ComputerPapers:
Extending the centerpoint theorem to multiple points. https://t.co/Bd0AwL84aD

None.

None.

Sample Sizes : None.

Authors: 2

Total Words: 8928

Unqiue Words: 1670

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.

ComputerPapers:
Polyline Drawings with Topological Constraints. https://t.co/bRt9P2T4JB

None.

None.

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

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible