ﻻ يوجد ملخص باللغة العربية
Let ${cal L}$ be an arrangement of $n$ lines in the Euclidean plane. The emph{$k$-level} of ${cal L}$ consists of all vertices $v$ of the arrangement which have exactly $k$ lines of ${cal L}$ passing below $v$. The complexity (the maximum size) of the $k$-level in a line arrangement has been widely studied. In 1998 Dey proved an upper bound of $O(ncdot (k+1)^{1/3})$. Due to the correspondence between lines in the plane and great-circles on the sphere, the asymptotic bounds carry over to arrangements of great-circles on the sphere, where the $k$-level denotes the vertices at distance at most $k$ to a marked cell, the emph{south pole}. We prove an upper bound of $O((k+1)^2)$ on the expected complexity of the $k$-level in great-circle arrangements if the south pole is chosen uniformly at random among all cells. We also consider arrangements of great $(d-1)$-spheres on the sphere $mathbb{S}^d$ which are orthogonal to a set of random points on $mathbb{S}^d$. In this model, we prove that the expected complexity of the $k$-level is of order $Theta((k+1)^{d-1})$.
We study the complexity of clustering curves under $k$-median and $k$-center objectives in the metric space of the Frechet distance and related distance measures. Building upon recent hardness results for the minimum-enclosing-ball problem under the
In this article, we provide new structural results and algorithms for the Homotopy Height problem. In broad terms, this problem quantifies how much a curve on a surface needs to be stretched to sweep continuously between two positions. More precisely
In this work, we show the first worst-case to average-case reduction for the classical $k$-SUM problem. A $k$-SUM instance is a collection of $m$ integers, and the goal of the $k$-SUM problem is to find a subset of $k$ elements that sums to $0$. In t
We introduce a model for random geodesic drawings of the complete bipartite graph $K_{n,n}$ on the unit sphere $mathbb{S}^2$ in $mathbb{R}^3$, where we select the vertices in each bipartite class of $K_{n,n}$ with respect to two non-degenerate probab
Assume you have a 2-dimensional pizza with $2n$ ingredients that you want to share with your friend. For this you are allowed to cut the pizza using several straight cuts, and then give every second piece to your friend. You want to do this fairly, t