Source author record

Jane Butterfield

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

ResearcherUnclaimed source record

Computational Geometry math.CO

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Line-of-Sight Pursuit in Monotone and Scallop Polygons

We study a turn-based game in a simply connected polygonal environment $Q$ between a pursuer $P$ and an adversarial evader $E$ . Both players can move in a straight line to any point within unit distance during their turn. The pursuer $P$ wins by capturing the evader, meaning that their distance satisfies $d(P, E) \leq 1$ , while the evader wins by eluding capture forever. Both players have a map of the environment, but they have different sensing capabilities. The evader $E$ always knows the location of $P$ . Meanwhile, $P$ only has line-of-sight visibility: $P$ observes the evader's position only when the line segment connecting them lies entirely within the polygon. Therefore $P$ must search for $E$ when the evader is hidden from view. We provide a winning strategy for $P$ in two families of polygons: monotone polygons and scallop polygons. In both families, a straight line $L$ can be moved continuously over $Q$ so that (1) $L \cap Q$ is a line segment and (2) every point on the boundary $\partial Q$ is swept exactly once. These are both subfamilies of strictly sweepable polygons. The sweeping motion for a monotone polygon is a single translation, and the sweeping motion for a scallop polygon is a single rotation. Our algorithms use rook's strategy during its pursuit phase, rather than the well-known lion's strategy. The rook's strategy is crucial for obtaining a capture time that is linear in the area of $Q$ . For both monotone and scallop polygons, our algorithm has a capture time of $O(n(Q) + \mbox{area}(Q))$, where $n(Q)$ is the number of polygon vertices.

preprint2015arXiv

Mantel's Theorem for Random Hypergraphs

A classical result in extremal graph theory is Mantel's Theorem, which states that every maximum triangle-free subgraph of $K_n$ is bipartite. A sparse version of Mantel's Theorem is that, for sufficiently large $p$ , every maximum triangle-free subgraph of $G(n,p)$ is w.h.p. bipartite. Recently, DeMarco and Kahn proved this for $p > K \sqrt{\log n/n}$ for some constant $K$ , and apart from the value of the constant this bound is best possible. We study an extremal problem of this type in random hypergraphs. Denote by $F_5$ , which sometimes called as the generalized triangle, the 3-uniform hypergraph with vertex set {a,b,c,d,e} and edge set {abc, ade, bde}. One of the first extremal results in extremal hypergraph theory is by Frankl and Füredi, who proved that the maximum 3-uniform hypergraph on n vertices containing no copy of $F_5$ is tripartite for n>3000. A natural question is for what p is every maximum $F_5$ -free subhypergraph of $G^3(n,p)$ w.h.p. tripartite. We show this holds for $p>K\log n/n$ for some constant K and does not hold for $p=0.1\sqrt{\log n}/n$ .

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.