Zobrazeno 1 - 10
of 29
pro vyhledávání: '"Ooms, Aurélien"'
We show an upper bound of $\frac{ \sin\left(\frac{3\pi}{10}\right) }{ \sin\left(\frac{2\pi}{5}\right)-\sin\left(\frac{3\pi}{10}\right) } <5.70$ on the spanning ratio of $\Theta_5$-graphs, improving on the previous best known upper bound of $9.96$ [Bo
Externí odkaz:
http://arxiv.org/abs/2106.01236
Autor:
Cardinal, Jean, Ooms, Aurélien
The sparse regression problem, also known as best subset selection problem, can be cast as follows: Given a set $S$ of $n$ points in $\mathbb{R}^d$, a point $y\in \mathbb{R}^d$, and an integer $2 \leq k \leq d$, find an affine combination of at most
Externí odkaz:
http://arxiv.org/abs/1908.00351
We consider the following problem: given three sets of real numbers, output a word-RAM data structure from which we can efficiently recover the sign of the sum of any triple of numbers, one in each set. This is similar to a previous work by some of t
Externí odkaz:
http://arxiv.org/abs/1903.02645
An "edge guard set" of a plane graph $G$ is a subset $\Gamma$ of edges of $G$ such that each face of $G$ is incident to an endpoint of an edge in $\Gamma$. Such a set is said to guard $G$. We improve the known upper bounds on the number of edges requ
Externí odkaz:
http://arxiv.org/abs/1804.07150
For most algorithms dealing with sets of points in the plane, the only relevant information carried by the input is the combinatorial configuration of the points: the orientation of each triple of points in the set (clockwise, counterclockwise, or co
Externí odkaz:
http://arxiv.org/abs/1801.01767
Autor:
Arseneva, Elena, Chiu, Man-Kwun, Korman, Matias, Markovic, Aleksandar, Okamoto, Yoshio, Ooms, Aurélien, van Renssen, André, Roeloffzen, Marcel
We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of $n$ vertices and $h$ holes. We introduce a \emph{graph of oriented distances} to encode the distance between pairs of poi
Externí odkaz:
http://arxiv.org/abs/1712.05538
Autor:
Aronov, Boris, Dujmović, Vida, Morin, Pat, Ooms, Aurélien, da Silveira, Luís Fernando Schultz Xavier
We study the following family of problems: Given a set of $n$ points in convex position, what is the maximum number triangles one can create having these points as vertices while avoiding certain sets of forbidden configurations. As forbidden configu
Externí odkaz:
http://arxiv.org/abs/1706.10193
The 3SUM problem asks if an input $n$-set of real numbers contains a triple whose sum is zero. We consider the 3POL problem, a natural generalization of 3SUM where we replace the sum function by a constant-degree polynomial in three variables. The mo
Externí odkaz:
http://arxiv.org/abs/1612.02384
The $k$-SUM problem is given $n$ input real numbers to determine whether any $k$ of them sum to zero. The problem is of tremendous importance in the emerging field of complexity theory within $P$, and it is in particular open whether it admits an alg
Externí odkaz:
http://arxiv.org/abs/1512.06678
Autor:
Arseneva, Elena, Chiu, Man-Kwun, Korman, Matias, Markovic, Aleksandar, Okamoto, Yoshio, Ooms, Aurélien, van Renssen, André, Roeloffzen, Marcel
Publikováno v:
In Computational Geometry: Theory and Applications January 2021 92