Let $P$ be a set of $n$ points in the plane. We consider a variation of the
classical Erd\H{o}s-Szekeres problem, presenting efficient algorithms with
$O(n^3)$ running time and $O(n^2)$ space complexity that compute: (1) A subset
$S$ of $P$ such that the boundary of the rectilinear convex hull of $S$ has the
maximum number of points from $P$, (2) a subset $S$ of $P$ such that the
boundary of the rectilinear convex hull of $S$ has the maximum number of points
from $P$ and its interior contains no element of $P$, (3) a subset $S$ of $P$
such that the rectilinear convex hull of $S$ has maximum area and its interior
contains no element of $P$, and (4) when each point of $P$ is assigned a
weight, positive or negative, a subset $S$ of $P$ that maximizes the total
weight of the points in the rectilinear convex hull of $S$.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 7

Total Words: 8478

Unqiue Words: 1484

In this paper, we study arrangements of orthogonal circles, that is,
arrangements of circles where every pair of circles must either be disjoint or
intersect at a right angle. Using geometric arguments, we show that such
arrangements have only a linear number of faces. This implies that orthogonal
circle intersection graphs have only a linear number of edges. When we restrict
ourselves to orthogonal unit circles, the resulting class of intersection
graphs is a subclass of penny graphs (that is, contact graphs of unit circles).
We show that, similarly to penny graphs, it is NP-hard to recognize orthogonal
unit circle intersection graphs.

more |
pdf
| html
None.

None.

None.

Sample Sizes : None.

Authors: 4

Total Words: 0

Unqiue Words: 0

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 160,435 papers.*

Sort results based on if they are interesting or reproducible.

Interesting

Reproducible