Source author record

Daniel Perz

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

ResearcherUnclaimed source record

Computational Geometry Discrete Mathematics math.CO

Catalog footprint

Research overview

4works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Finding a Battleship of Uncertain Shape

Motivated by a game of Battleship, we consider the problem of efficiently hitting a ship of an uncertain shape within a large playing board. Formally, we fix a dimension $d\in\{1,2\}$ . A ship is a subset of $\mathbb{Z}^d$ . Given a family $F$ of ships, we say that an infinite subset $X\subset\mathbb{Z}^d$ of the cells pierces $F$ , if it intersects each translate of each ship in $F$ (by a vector in $\mathbb{Z}^d$ ). In this work, we study the lowest possible (asymptotic) density $π(F)$ of such a piercing subset. To our knowledge, this problem has previously been studied only in the special case $|F|=1$ (a single ship). As our main contribution, we present a formula for $π(F)$ when $F$ consists of 2 ships of size 2 each, and we identify the toughest families in several other cases. We also implement an algorithm for finding $π(F)$ in 1D.

preprint2022arXiv

On Compatible Matchings

A matching is compatible to two or more labeled point sets of size $n$ with labels $\{1,\dots,n\}$ if its straight-line drawing on each of these point sets is crossing-free. We study the maximum number of edges in a matching compatible to two or more labeled point sets in general position in the plane. We show that for any two labeled convex sets of $n$ points there exists a compatible matching with $\lfloor \sqrt {2n}\rfloor$ edges. More generally, for any $\ell$ labeled point sets we construct compatible matchings of size $Ω(n^{1/\ell})$ . As a corresponding upper bound, we use probabilistic arguments to show that for any $\ell$ given sets of $n$ points there exists a labeling of each set such that the largest compatible matching has ${\mathcal{O}}(n^{2/({\ell}+1)})$ edges. Finally, we show that $Θ(\log n)$ copies of any set of $n$ points are necessary and sufficient for the existence of a labeling such that any compatible matching consists only of a single edge.

preprint2020arXiv

Empty Rainbow Triangles in $k$ -colored Point Sets

Let $S$ be a set of $n$ points in general position in the plane. Suppose that each point of $S$ has been assigned one of $k \ge 3$ possible colors and that there is the same number, $m$ , of points of each color class. A polygon with vertices on $S$ is empty if it does not contain points of $S$ in its interior; and it is rainbow if all its vertices have different colors. Let $f(k,m)$ be the minimum number of empty rainbow triangles determined by $S$ . In this paper we give tight asymptotic bounds for this function. Furthermore, we show that $S$ may not determine an empty rainbow quadrilateral for some arbitrarily large values of $k$ and $m$ .

preprint2020arXiv

Plane Spanning Trees in Edge-Colored Simple Drawings of $K_n$

Károlyi, Pach, and Tóth proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple drawings of the complete graph. These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once. We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings. (In a cylindrical drawing, all vertices are placed on two concentric circles and no edge crosses either circle.) Second, we introduce a relaxation of the problem in which the graph is $k$ -edge-colored, and the target structure must be hypochromatic, that is, avoid (at least) one color class. In this setting, we show that every $\lceil (n+5)/6\rceil$ -edge-colored monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree. (In a monotone drawing, every edge is represented as an $x$ -monotone curve.)

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.

Daniel Perz

Research overview

Is this your work?

4 publications

Finding a Battleship of Uncertain Shape

On Compatible Matchings

Empty Rainbow Triangles in $k$ -colored Point Sets

Plane Spanning Trees in Edge-Colored Simple Drawings of $K_n$

See the researcher in context

Building this map preview

Daniel Perz

Research overview

Is this your work?

4 publications

Finding a Battleship of Uncertain Shape

On Compatible Matchings

Empty Rainbow Triangles in kkk-colored Point Sets

Plane Spanning Trees in Edge-Colored Simple Drawings of KnK_nKn​

See the researcher in context

Building this map preview

Empty Rainbow Triangles in $k$ -colored Point Sets

Plane Spanning Trees in Edge-Colored Simple Drawings of $K_n$