BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Pablo Pérez-Lantero

Pablo Pérez-Lantero appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Computational Geometrymath.COData Structures and AlgorithmsComputational Complexitymath.MG

Catalog footprint

What is connected

16works
5topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

16 published item(s)

preprint2023arXiv

Center of maximum-sum matchings of bichromatic points

Let $R$ and $B$ be two disjoint point sets in the plane with $|R|=|B|=n$. Let $\mathcal{M}=\{(r_i,b_i),i=1,2,\ldots,n\}$ be a perfect matching that matches points of $R$ with points of $B$ and maximizes $\sum_{i=1}^n\|r_i-b_i\|$, the total Euclidean distance of the matched pairs. In this paper, we prove that there exists a point $o$ of the plane (the center of $\mathcal{M}$) such that $\|r_i-o\|+\|b_i-o\|\le \sqrt{2}~\|r_i-b_i\|$ for all $i\in\{1,2,\ldots,n\}$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Rectilinear Convex Hull of Points in 3D

Let $P$ be a set of $n$ points in $\mathbb{R}^3$ in general position, and let $RCH(P)$ be the rectilinear convex hull of $P$. In this paper we obtain an optimal $O(n\log n)$-time and $O(n)$-space algorithm to compute $RCH(P)$. We also obtain an efficient $O(n\log^2 n)$-time and $O(n\log n)$-space algorithm to compute and maintain the set of vertices of the rectilinear convex hull of $P$ as we rotate $\mathbb R^3$ around the $z$-axis. Finally we study some properties of the rectilinear convex hulls of point sets in $\mathbb{R}^3$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Non-crossing Monotone Paths and Binary Trees in Edge-ordered Complete Geometric Graphs

An edge-ordered graph is a graph with a total ordering of its edges. A path $P=v_1v_2\ldots v_k$ in an edge-ordered graph is called increasing if $(v_iv_{i+1}) > (v_{i+1}v_{i+2})$ for all $i = 1,\ldots,k-2$; it is called decreasing if $(v_iv_{i+1}) < (v_{i+1}v_{i+2})$ for all $i = 1,\ldots,k-2$. We say that $P$ is monotone if it is increasing or decreasing. A rooted tree $T$ in an edge-ordered graph is called monotone if either every path from the root of to a leaf is increasing or every path from the root to a leaf is decreasing. Let $G$ be a graph. In a straight-line drawing $D$ of $G$, its vertices are drawn as different points in the plane and its edges are straight line segments. Let $\overlineα(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing path of length $\overlineα(G)$. Let $\overlineτ(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing complete binary tree of size $\overlineτ(G)$. In this paper we show that $\overline α(K_n) = Ω(\log\log n)$, $\overline α(K_n) = O(\log n)$, $\overline τ(K_n) = Ω(\log\log \log n)$ and $\overline τ(K_n) = O(\sqrt{n \log n})$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Drawing the Almost Convex Set in an Integer Grid of Minimum Size

In 2001, Károlyi, Pach and Tóth introduced a family of point sets to solve an Erdős-Szekeres type problem; which have been used to solve several other Edős-Szekeres type problems. In this paper we refer to these sets as nested almost convex sets. A nested almost convex set $\mathcal{X}$ has the property that the interior of every triangle determined by three points in the same convex layer of $\mathcal{X}$, contains exactly one point of $\mathcal{X}$. In this paper, we introduce a characterization of nested almost convex sets. Our characterization implies that there exists at most one (up to order type) nested almost convex set of $n$ points. We use our characterization to obtain a linear time algorithm to construct nested almost convex sets of $n$ points, with integer coordinates of absolute values at most $O(n^{\log_2 5})$. Finally, we use our characterization to obtain an $O(n\log n)$-time algorithm to determine whether a set of points is a nested almost convex set.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Linear Separability in Spatial Databases

Given two point sets $R$ and $B$ in the plane, with cardinalities $m$ and $n$, respectively, and each set stored in a separate R-tree, we present an algorithm to decide whether $R$ and $B$ are linearly separable. Our algorithm exploits the structure of the R-trees, loading into the main memory only relevant data, and runs in $O(m\log m + n\log n)$ time in the worst case. As experimental results, we implement the proposed algorithm and executed it on several real and synthetic point sets, showing that the percentage of nodes of the R-trees that are accessed and the memory usage are low in these cases. We also present an algorithm to compute the convex hull of $n$ planar points given in an R-tree, running in $O(n\log n)$ time in the worst case.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

The intersection graph of the disks with diameters the sides of a convex $n$-gon

Given a convex polygon of $n$ sides, one can draw $n$ disks (called side disks) where each disk has a different side of the polygon as diameter and the midpoint of the side as its center. The intersection graph of such disks is the undirected graph with vertices the $n$ disks and two disks are adjacent if and only if they have a point in common. We prove that for every convex polygon this graph is planar. Particularly, for $n=5$, this shows that for any convex pentagon there are two disks among the five side disks that do not intersect, which means that $K_5$ is never the intersection graph of such five disks. For $n=6$, we then have that for any convex hexagon the intersection graph of the side disks does not contain $K_{3,3}$ as subgraph.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Adaptive Computation of the Klee's Measure in High Dimensions

The KLEE'S MESURE of $n$ axis-parallel boxes in $\mathbb{R}^d$ is the volume of their union. It can be computed in time within $O(n^{d/2})$ in the worst case. We describe three techniques to boost its computation: one based on some type of "degeneracy'' of the input, and two ones on the inherent "easiness'' of the structure of the input. The first technique benefits from instances where the MAXIMA of the input is of small size $h$, and yields a solution running in time within $O(n\log^{2d-2}{h}+ h^{d/2}) \subseteq O(n^{d/2}$). The second technique takes advantage of instances where no $d$-dimensional axis-aligned hyperplane intersects more than $k$ boxes in some dimension, and yields a solution running in time within $O(n \log n + n k^{(d-2)/2}) \subseteq O(n^{d/2})$. The third technique takes advantage of instances where the \emph{intersection graph} of the input has small treewidth $ω$. It yields an algorithm running in time within $O(n^4ω\log ω+ n (ω\log ω)^{d/2})$ in general, and in time within $O(n \log n + n ω^{d/2})$ if an optimal tree decomposition of the intersection graph is given. We show how to combine these techniques in an algorithm which takes advantage of all three configurations.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Adaptive Computation of the Swap-Insert Correction Distance

The Swap-Insert Correction distance from a string $S$ of length $n$ to another string $L$ of length $m\geq n$ on the alphabet $[1..d]$ is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting $S$ into $L$. Contrarily to other correction distances, computing it is NP-Hard in the size $d$ of the alphabet. We describe an algorithm computing this distance in time within $O(d^2 nm g^{d-1})$, where there are $n_α$ occurrences of $α$ in $S$, $m_α$ occurrences of $α$ in $L$, and where $g=\max_{α\in[1..d]} \min\{n_α,m_α-n_α\}$ measures the difficulty of the instance. The difficulty $g$ is bounded by above by various terms, such as the length of the shortest string $S$, and by the maximum number of occurrences of a single character in $S$. Those results illustrate how, in many cases, the correction distance between two strings can be easier to compute than in the worst case scenario.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Area and Perimeter of the Convex Hull of Stochastic Points

Given a set $P$ of $n$ points in the plane, we study the computation of the probability distribution function of both the area and perimeter of the convex hull of a random subset $S$ of $P$. The random subset $S$ is formed by drawing each point $p$ of $P$ independently with a given rational probability $π_p$. For both measures of the convex hull, we show that it is \#P-hard to compute the probability that the measure is at least a given bound $w$. For $\varepsilon\in(0,1)$, we provide an algorithm that runs in $O(n^{6}/\varepsilon)$ time and returns a value that is between the probability that the area is at least $w$, and the probability that the area is at least $(1-\varepsilon)w$. For the perimeter, we show a similar algorithm running in $O(n^{6}/\varepsilon)$ time. Finally, given $\varepsilon,δ\in(0,1)$ and for any measure, we show an $O(n\log n+ (n/\varepsilon^2)\log(1/δ))$-time Monte Carlo algorithm that returns a value that, with probability of success at least $1-δ$, differs at most $\varepsilon$ from the probability that the measure is at least $w$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Interval Selection in the Streaming Model

A set of intervals is independent when the intervals are pairwise disjoint. In the interval selection problem we are given a set $\mathbb{I}$ of intervals and we want to find an independent subset of intervals of largest cardinality. Let $α(\mathbb{I})$ denote the cardinality of an optimal solution. We discuss the estimation of $α(\mathbb{I})$ in the streaming model, where we only have one-time, sequential access to the input intervals, the endpoints of the intervals lie in $\{1,...,n \}$, and the amount of the memory is constrained. For intervals of different sizes, we provide an algorithm in the data stream model that computes an estimate $\hatα$ of $α(\mathbb{I})$ that, with probability at least $2/3$, satisfies $\tfrac 12(1-\varepsilon) α(\mathbb{I}) \le \hatα\le α(\mathbb{I})$. For same-length intervals, we provide another algorithm in the data stream model that computes an estimate $\hatα$ of $α(\mathbb{I})$ that, with probability at least $2/3$, satisfies $\tfrac 23(1-\varepsilon) α(\mathbb{I}) \le \hatα\le α(\mathbb{I})$. The space used by our algorithms is bounded by a polynomial in $\varepsilon^{-1}$ and $\log n$. We also show that no better estimations can be achieved using $o(n)$ bits of storage. We also develop new, approximate solutions to the interval selection problem, where we want to report a feasible solution, that use $O(α(\mathbb{I}))$ space. Our algorithms for the interval selection problem match the optimal results by Emek, Halld{ó}rsson and Ros{é}n [Space-Constrained Interval Selection, ICALP 2012], but are much simpler.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Independent and Hitting Sets of Rectangles Intersecting a Diagonal Line : Algorithms and Complexity

Finding a maximum independent set (MIS) of a given fam- ily of axis-parallel rectangles is a basic problem in computational geom- etry and combinatorics. This problem has attracted significant atten- tion since the sixties, when Wegner conjectured that the corresponding duality gap, i.e., the maximum possible ratio between the maximum independent set and the minimum hitting set (MHS), is bounded by a universal constant. An interesting special case, that may prove use- ful to tackling the general problem, is the diagonal-intersecting case, in which the given family of rectangles is intersected by a diagonal. Indeed, Chepoi and Felsner recently gave a factor 6 approximation algorithm for MHS in this setting, and showed that the duality gap is between 3/2 and 6. In this paper we improve upon these results. First we show that MIS in diagonal-intersecting families is NP-complete, providing one smallest subclass for which MIS is provably hard. Then, we derive an $O(n^2)$-time algorithm for the maximum weight independent set when, in addition the rectangles intersect below the diagonal. This improves and extends a classic result of Lubiw, and amounts to obtain a 2-approximation algo- rithm for the maximum weight independent set of rectangles intersecting a diagonal. Finally, we prove that for diagonal-intersecting families the duality gap is between 2 and 4. The upper bound, which implies an approximation algorithm of the same factor, follows from a simple com- binatorial argument, while the lower bound represents the best known lower bound on the duality gap, even in the general case.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

New results on stabbing segments with a polygon

We consider a natural variation of the concept of stabbing a segment by a simple polygon: a segment is stabbed by a simple polygon $\mathcal{P}$ if at least one of its two endpoints is contained in $\mathcal{P}$. A segment set $S$ is stabbed by $\mathcal{P}$ if every segment of $S$ is stabbed by $\mathcal{P}$. We show that if $S$ is a set of pairwise disjoint segments, the problem of computing the minimum perimeter polygon stabbing $S$ can be solved in polynomial time. We also prove that for general segments the problem is NP-hard. Further, an adaptation of our polynomial-time algorithm solves an open problem posed by Löffler and van Kreveld [Algorithmica 56(2), 236--269 (2010)] about finding a maximum perimeter convex hull for a set of imprecise points modeled as line segments.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Drawing the double circle on a grid of minimum size

In 1926, Jarník introduced the problem of drawing a convex $n$-gon with vertices having integer coordinates. He constructed such a drawing in the grid $[1,c\cdot n^{3/2}]^2$ for some constant $c>0$, and showed that this grid size is optimal up to a constant factor. We consider the analogous problem for drawing the double circle, and prove that it can be done within the same grid size. Moreover, we give an O(n)-time algorithm to construct such a point set.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Locating a single facility and a high-speed line

In this paper we study a facility location problem in the plane in which a single point (facility) and a rapid transit line (highway) are simultaneously located in order to minimize the total travel time from the clients to the facility, using the $L_1$ or Manhattan metric. The rapid transit line is given by a segment with any length and orientation, and is an alternative transportation line that can be used by the clients to reduce their travel time to the facility. We study the variant of the problem in which clients can enter and exit the highway at any point. We provide an $O(n^3)$-time algorithm that solves this variant, where $n$ is the number of clients. We also present a detailed characterization of the solutions, which depends on the speed given in the highway.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On the number of radial orderings of planar point sets

Given a set $S$ of $n$ points in the plane, a \emph{radial ordering} of $S$ with respect to a point $p$ (not in $S$) is a clockwise circular ordering of the elements in $S$ by angle around $p$. If $S$ is two-colored, a \emph{colored radial ordering} is a radial ordering of $S$ in which only the colors of the points are considered. In this paper, we obtain bounds on the number of distinct non-colored and colored radial orderings of $S$. We assume a strong general position on $S$, not three points are collinear and not three lines---each passing through a pair of points in $S$---intersect in a point of $\R^2\setminus S$. In the colored case, $S$ is a set of $2n$ points partitioned into $n$ red and $n$ blue points, and $n$ is even. We prove that: the number of distinct radial orderings of $S$ is at most $O(n^4)$ and at least $Ω(n^3)$; the number of colored radial orderings of $S$ is at most $O(n^4)$ and at least $Ω(n)$; there exist sets of points with $Θ(n^4)$ colored radial orderings and sets of points with only $O(n^2)$ colored radial orderings.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The 1-Center and 1-Highway problem

We study a variation of the 1-center problem in which, in addition to a single supply facility, we are allowed to locate a highway. This highway increases the transportation speed between any demand point and the facility. That is, given a set $S$ of points and $v>1$, we are interested in locating the facility point $f$ and the highway $h$ that minimize the expression $\max_{p\in S}d_{h}(p,f)$, where $d_h$ is the time needed to travel between $p$ and $f$. We consider two types of highways ({\em freeways} and {\em turnpikes}) and study the cases in which the highway's length is fixed by the user (or can be modified to further decrease the transportation time).

0 citations0 reviewsNo code linkedOpen access