Source author record

David Flores-Peñaloza

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Geometry Discrete Mathematics

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2015arXiv

Modem Illumination of Monotone Polygons

We study a generalization of the classical problem of the illumination of polygons. Instead of modeling a light source we model a wireless device whose radio signal can penetrate a given number $k$ of walls. We call these objects $k$ -modems and study the minimum number of $k$ -modems sufficient and sometimes necessary to illuminate monotone and monotone orthogonal polygons. We show that every monotone polygon with $n$ vertices can be illuminated with $\big\lceil \frac{n-2}{2k+3} \big\rceil$ $k$ -modems. In addition, we exhibit examples of monotone polygons requiring at least $\lceil \frac {n-2} {2k+3}\rceil$ $k$ -modems to be illuminated. For monotone orthogonal polygons with $n$ vertices we show that for $k=1$ and for even $k$ , every such polygon can be illuminated with $\big\lceil \frac{n-2}{2k+4} \big\rceil$ $k$ -modems, while for odd $k\geq3$ , $\big\lceil \frac{n-2}{2k+6} \big\rceil$ $k$ -modems are always sufficient. Further, by presenting according examples of monotone orthogonal polygons, we show that both bounds are tight.

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.

preprint2012arXiv

On the Connectedness and Diameter of a Geometric Johnson Graph

Let $P$ be a set of $n$ points in general position in the plane. A subset $I$ of $P$ is called an \emph{island} if there exists a convex set $C$ such that $I = P \cap C$ . In this paper we define the \emph{generalized island Johnson graph} of $P$ as the graph whose vertex consists of all islands of $P$ of cardinality $k$ , two of which are adjacent if their intersection consists of exactly $l$ elements. We show that for large enough values of $n$ , this graph is connected, and give upper and lower bounds on its diameter.

preprint2009arXiv

Token Graphs

For a graph $G$ and integer $k\geq1$ , we define the token graph $F_k(G)$ to be the graph with vertex set all $k$ -subsets of $V(G)$ , where two vertices are adjacent in $F_k(G)$ whenever their symmetric difference is a pair of adjacent vertices in $G$ . Thus vertices of $F_k(G)$ correspond to configurations of $k$ indistinguishable tokens placed at distinct vertices of $G$ , where two configurations are adjacent whenever one configuration can be reached from the other by moving one token along an edge from its current position to an unoccupied vertex. This paper introduces token graphs and studies some of their properties including: connectivity, diameter, cliques, chromatic number, Hamiltonian paths, and Cartesian products of token graphs.

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.