Guillermo Esteban

Sarita de Berg, Guillermo Esteban, Rodrigo I. Silveira et al.

In this paper, we consider the Weighted Region Problem. In the Weighted Region Problem, the length of a path is defined as the sum of the weights of the subpaths within each region, where the weight of a subpath is its Euclidean length multiplied by a weight $ α\geq 0 $ depending on the region. We study a restricted version of the problem of determining shortest paths through a single weighted rectangular region. We prove that even this very restricted version of the problem is unsolvable within the Algebraic Computation Model over the Rational Numbers (ACMQ). On the positive side, we provide the equations for the shortest paths that are computable within the ACMQ. Additionally, we provide equations for the bisectors between regions of the Shortest Path Map for a source point on the boundary of (or inside) the rectangular region.

Prosenjit Bose, Guillermo Esteban, David Orden et al.

Let $ Π(n) $ be the largest number such that for every set $ S $ of $ n $ points in a polygon~$ P $, there always exist two points $ x, y \in S $, where every geodesic disk containing $ x $ and $ y $ contains $ Π(n) $ points of~$ S $. We establish upper and lower bounds for $ Π(n)$, and show that $ \left\lceil \frac{n}{5}\right\rceil+1 \leq Π(n) \leq \left\lceil \frac{n}{4} \right\rceil +1 $. We also show that there always exist two points $x, y\in S$ such that every geodesic disk with $x$ and $y$ on its boundary contains at least $ \frac{n}{7+\sqrt{37}} \approx \left\lceil \frac{n}{13.1} \right\rceil$ points both inside and outside the disk. For the special case where the points of $ S $ are restricted to be the vertices of a geodesically convex polygon we give a tight bound of $\left\lceil \frac{n}{3} \right\rceil + 1$. We provide the same tight bound when we only consider geodesic disks having $ x $ and $ y $ as diametral endpoints. We give upper and lower bounds of $\left\lceil \frac{n}{5} \right\rceil + 1 $ and $\frac{n}{6+\sqrt{26}} \approx \left\lceil \frac{n}{11.1} \right\rceil$, respectively, for the two-colored version of the problem. Finally, for the two-colored variant we show that there always exist two points $x, y\in S$ where $x$ and $y$ have different colors and every geodesic disk with $x$ and $y$ on its boundary contains at least $\left\lceil \frac{n}{27.1}\right\rceil+1$ points both inside and outside the disk.