The recognition problem for penny graphs, contact graphs of unit disks in the plane, has been known to be NP-hard since the work by Breu and Kirkpatrick in the 90s. In this talk we settle the complexity of the problem by showing it is exactly as hard as deciding truth in the existential theory of the reals (ER). We will also give an introduction and overview of the recent complexity class ER.

We study the problem of simultaneous geometric embedding of two paths without self-intersections on an integer grid. We show that minimizing the length of the longest edge of such an embedding is NP-hard. We also show that we can minimize in $O(n^{3/2})$ time the perimeter of an integer grid containing such an embedding if one path is $x$-monotone and the other is $y$-monotone.

Simplicial approximation provides a framework for constructing simplicial complexes that are homotopy equivalent to a given manifold, provided a CW structure is explicitly known. However, its conventional implementation quickly becomes intractable on a computer: barycentric subdivision produces poorly shaped simplices, and the star condition introduces many vertices. To address these limitations, this article develops a subdivision scheme based on spherical Delaunay triangulations, which attains better refinement properties than barycentric subdivisions. Moreover, the star condition is reframed as two independent problems, one geometric and another combinatorial, respectively tackled in the language of local motion planners and the list homomorphism problem, allowing an exponential gain in the number of vertices. Via a prototype implementation, we obtain simplicial complexes provably homotopy equivalent to Grassmannians and Stiefel manifolds up to dimension 5.

In this work, we introduce t-colorable k-plane drawings}, that is, drawings of graphs with a t-edge-coloring where every edge is crossed by at most k~edges of each color. We give tight upper bounds on the edge- and crossing density for small values of~t and~k and show that the recognition of such drawings is NP-complete if t≥2 and k≥1.

Let $S$ be a set of $N$ points in the plane in general position. The Voronoi diagram of order $k$, denoted by $V_k(S)$, is a partition of the plane into faces, where all the points inside a face have the same set of $k$ nearest points from $S$. In this paper, we study upper bounds on the maximum number of quadrilateral faces, denoted by $q_k(S)$, that $V_k(S)$ can contain. In particular, we show that for $2\le k\le N-2$, \[q_k(S) \le \min \left\{ \frac{k(2N-k-1)-\sum_{j=0}^{k-1}e_j}{2}, \frac{(k-1)(2N-k)-\sum_{j=0}^{k-2}e_j}{2} \right\}\] where $e_j$ denotes the number of $j$-edges of $S$, and a $j$-edge is a half-plane defined by the oriented line through a pair of points of $S$ that contains $j$ points of $S$ in its interior. Furthermore, we also show some other upper bounds and the tightness of the upper bounds in some cases.

We introduce the notion of the simple topological thickness of a graph G as the smallest number of colors required to produce an edge-colored simple drawing of G without monochromatic crossings. A drawing is simple if adjacent edges do not cross and any two independent edges cross at most once. We show that simple topological thickness is different from geometric thickness and (graph) thickness. In particular, we show that the simple topological thickness of 2-degenerate graphs is at most two and there exists a biplanar graph with simple topological thickness at least three.

Let $ \Pi(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 $ \Pi(n) $ points of~$ S $. We establish a lower bound for $ \Pi(n)$, and show that $ \left\lceil \frac{n}{5}\right\rceil+1 \leq \Pi(n) $. 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.

In this work, we study a variant of the geometric graph thickness problem according to which the edge lengths are strictly increasing from one layer to the next.

In this work we study the problem of reconstructing a Laguerre tessellation from the volumes and the barycenters of its cells. We show that any vector of barycenters arising from a Laguerre tessellation with prescribed cell volumes can be understood as an exposed point of a convex set defined by convex order relations. Leveraging this characterization, we formulate a projection problem that can be solved efficiently and yields an approximation of the desired reconstruction.

Storyline layouts visualize temporal interactions by drawing each character as an $x$-monotone curve and enforcing that the participants of every meeting form a contiguous vertical group. We study a drawing extension variant in which a layout of a sub-storyline is fixed and has to be extended by inserting missing characters while preserving all meeting constraints. We minimize the local crossing number $\chi$, i.e., the maximum number of crossings along any single character. We prove that the problem is W[1]-hard parameterized by the number $k$ of inserted characters plus the maximum number $\sigma$ of active characters, in XP parameterized by $\sigma$ and in FPT parameterized by~$\sigma+\chi$.

Motivated by targeted drug delivery, we investigate the gathering of particles in the full tilt model of externally controlled motion planning: A set of particles is located at the tiles of a polyomino. They react uniformly to an external force by moving maximally in one of the four axis-parallel directions until they hit the boundary. The goal is to choose a sequence of directions that moves all particles to a common position. We show how to compute gathering sequences for filled polyominoes and prove it PSPACE-complete to determine if the particles in a partially filled polyomino can be gathered. The results build on a connection we establish between tilt models and synchronizing automata.

This paper makes contributions to the theory of crossing numbers of complete graphs. An {antipodal pair} in a drawing is a pair of vertices such that the stars of the two vertices induce a plane subgraph of the drawing. An {optimal} drawing of a graph is a drawing with a minimum number of crossings. We conjecture that optimal drawings of complete graphs with {n>14} vertices have antipodal pairs. If true this implies Hill's conjecture: cr(K_n) = H(n) = 1/4\lfloor{n}/{2}\rfloor\lfloor{n-1}/{2}\rfloor\lfloor{n-2}/{2}\rfloor\lfloor{n-3}/{2}\rfloor. Our second main contribution is the construction of a new family of Hill drawings, i.e., a family of drawings of {K_n} with crossing number equal to H(n). A consequence of this new construction is that every spherical drawing of {K_k} is a subdrawing of a Hill drawing of {K_n} for all {n \geq 2k+1}.

We investigate the problem of optimally partitioning a given polyomino-shaped area into a disjoint set of connected subareas, such that a team of simple robots can build it in shortest possible time. Each subarea must contain its own depot from a given set, which supplies the robots with tile-sized building material. A robot can carry one tile at a time from its supply depot to a new position, while moving on existing tiles of its subconfiguration. As a result, the cost for constructing a subarea corresponds to the sum of distances from its respective depot to all of its tile sites and the total cost is the cost of the most expensive subarea. We provide hardness results for two variants of the resulting clustering problem. For given depots, it is NP-hard to decide if tiles can be assigned to the depots with a maximum cost of 3, even for rectangular instances. If the depot locations can be chosen, the problem is already hard for a maximum cost of 2. For lower costs, both variants are in P.

Let $P$ be a generic set of $n$ points in the plane, and let $P=R\cup B$ be a coloring of $P$ in two colors. We are interested in the number of crossings between the minimum spanning trees of $R$ and $B$, denoted by $\crossAB(R,B)$. We define the \emph{bicolored MST crossing number} of $P$, denoted by $\cross(P)$, as $\cross(P) = \max_{P= R\cup B}(\crossAB(R,B))$. We prove a linear upper bound for $\cross(P)$ when $P$ is generic. If $P$ is dense or in convex position, we provide linear lower bounds.

We study the classic \newterm{sliding cube model} for programmable matter under parallel reconfiguration in three dimensions. This problem asks for discrete reconfiguration sequences between two connected configurations of n indistinguishable cube modules under connectivity constraints; the makespan of such a sequence is the number of parallel operations performed. We show that deciding the existence of such a sequence is NP-hard to decide for constant makespan even if the two input configurations have constant-size symmetric difference, solving an open question in [Akitaya et al., ESA 25]. We also show logAPX-hardness of the problem in sequential and parallel models, strengthening the APX-hardness claim in [Akitaya et al., SWAT 22]. Finally, we give an asymptotically worst-case optimal input-sensitive algorithm for reconfiguration, where the makespan, which is O(n) in the worst~case, depends on the bounding box of the input.

We study the existence of plane substructures in rectilinear drawings of the hypercube graph $Q_d$. We construct drawings of $Q_d$ which contain no plane subgraph with more than $2d-2$ edges, no plane path with more than $2d-3$ edges, and no plane matching of size more than $2d-4$. On the other hand, we prove that every rectilinear drawing of $Q_d$ with vertices in convex position contains a plane path of length $d-1$ (if $d$ is odd) or $d$ (if $d$ is even). We also prove that if a graph $G$ is contained in every drawing of $Q_d$ for a sufficiently large $d$, then $G$ is necessarily a forest of caterpillars. Lastly, we give a short proof of a generalization of a result by Alpert et al. on the maximum rectilinear crossing number of $Q_d$.

Multi-robot motion planning is a hard problem. We investigate variants of the problem where square robots are allowed to move only a constant number of times each. We show that the problem remains NP-hard in most cases, except when the squares have unit size and when the problem is unlabeled, i.e. each square can go to an arbitrary target.

Recently, a natural variant of the Art Gallery problem, known as the \emph{Contiguous Art Gallery problem} was proposed. Given a simple polygon $P$ with $n$ vertices, the goal is to partition its boundary $\partial P$ into the smallest number of contiguous segments such that each segment is completely visible from some point in $P$. Unlike the classical Art Gallery problem, which is NP-hard, this variant is polynomial-time solvable as show by three independent works at SoCG '25. Interestingly, these results were obtained using entirely different approaches, yet all led to roughly the same high asymptotic complexity. In this paper, we show a simple but strong structural theorem that defines a linear-size set starting locations $X$, such that for at least one $u \in X$, a greedy algorithm that starts at $u$ finds an optimal solution. Together with an $O(n\log n)$ time algorithm to compute $X$, this directly improves the running time of previous algorithms by a quadratic factor, resulting in an $O(n^3 \log n)$ algorithm for the Contiguous Art Gallery problem.

We consider a special, geometric case of a balancing game introduced by Spencer in 1977. Consider any arrangement $\mathcal{L}$ of $n$ lines in the plane, and assume that each cell of the arrangement contains a box. Alice initially places pebbles in each box. In each subsequent step, Bob picks a line, and Alice must choose a side of that line, remove one pebble from each box on that side, and add one pebble to each box on the other side. Bob wins if any box ever becomes empty. We determine the minimum number $f(\mathcal L)$ of pebbles, computable in polynomial time, for which Alice can prevent Bob from ever winning, and we show that $f(\mathcal L)=\Theta(n^3)$ for any arrangement $\mathcal{L}$ of $n$ lines in general position.

We investigate the Dispersive Art Gallery Problem with vertex guards for a class of orthogonal polygons that reflect the properties of real-world floor plans: These office-like polygons consist of rectangular rooms and corridors. In the dispersive variant of the Art Gallery Problem, the objective is not to minimize the number of guards but to maximize the minimum distance between any pair of guards, called the dispersion distance. We prove that determining whether a guard set can achieve a dispersion distance of 4 in office-like polygons, where vertices are restricted to integer coordinates, is NP-complete. Complementarily, we present a simple worst-case optimal algorithm that guarantees a dispersion distance of 3. For the more restricted class of hole-free independent office-like polygons, we propose a dynamic programming approach that computes optimal solutions in polynomial time.

Wataridori is a pencil puzzle involving drawing paths to connect all circles in a rectangular grid into pairs, in order to satisfy several constraints. In this paper, we prove that deciding solvability of a given Wataridori puzzle is NP-complete via reduction from Numberlink, another pencil puzzle that has already been proved to be NP-complete.

The chromatic dispersive art gallery problem (CDAGP) asks for a guard cover in which guards of the same color have a distance of at least d. We consider the CDAGP for two colors in polyominoes. We provide an algorithm to compute a cover when d = 3, and show that the problem is NP-complete in polyominoes with holes for d = 5.

All or Nothing, Water Walk, and Remembered Length are pencil puzzles that involve constructing a continuous loop on a rectangular grid under specific constraints. In this paper, we analyze their computational complexity using the T-metacell framework developed by Tang and MIT Hardness Group. We establish that the puzzles are NP-complete by providing reductions; the first two puzzles, from the problem of finding a Hamiltonian cycle in a maximum-degree-3 spanning subgraph of a rectangular grid graph, and the last, from the problem of finding a Hamiltonian cycle in a required-edge directed rectangular grid graph.

We study the minmax watchman route problem for two watchmen. We present an approximation algorithm to see a discrete set of m points in the interior of P with approximation ratio 2 + ε taking O(m^5n) time. We generalize the algorithm to see all of the interior of P in O(n^6) time with approximation ratio 2 + π/2 = 3.570..., improving on the previously known best algorithm that has an approximation ratio of 6.922... and runtime O(n^2) [5].

We introduce the complexity class Quantified Reals abbreviated as QR. Let FOTR be the set of true sentences in the first-order theory of the reals. A language $L$ is in QR, if there is a polynomial time reduction from $L$ to FOTR. To the best of our knowledge, this is the first time this complexity class is studied. We show that QR can also be defined using real Turing machines or the real RAM. Interestingly, it is known that deciding FOTR requires at least exponential time unconditionally[Berman, Theoretical Computer Science, 1980]. We focus on so-called Devil's games that have two defining properties: (1) Players alternate in taking turns and (2) each turn gives an infinite continuum of possible options. The two players are referred to as human and devil. Our paper presents four QR-complete problems. First, we show that FOTR-INV is QR-complete. FOTR-INV has only inversion and addition constraints and all variables are contained in a bounded range. FOTR-INV is a stepping stone for further reductions. Second, we show that the Packing Game is QR-complete. In the Packing Game we are given a container, as a polygonal domain and two sets of polygons, called pieces. One set of pieces for the human and one set for the devil. The human and the devil alternate by removing one of their pieces and placing it into the container. Both rotations and translations are allowed. The first player who cannot place a piece into the container loses. If all pieces can be placed the human wins. Third, we show that the Planar Extension Game is QR-complete. In this game, we are given a partially drawn plane graph and the human and the devil alternate by placing vertices and the corresponding edges in a straight-line manner. The vertices and edges to be placed are prescribed beforehand and known to both players. The first player who cannot place a vertex while respecting planarity of the drawing loses. If all the vertices can be placed the human wins. Finally, we show that the Order Type Game is QR-complete. In this game, we are given an order type together with a linear order of the abstract points. The human and the devil alternate in placing a point in the Euclidean plane $R^2$ following the linear order. The first player who cannot place a point respecting the order type loses. If all the points can be placed the human wins.

We develop an O(m^7n) time 6 + ϵ approximation algorithm for the minmax three-visiting routes problem in a simple n vertex polygon, i.e., given three starting points and a collection of m point sized treasures in the polygon, compute three closed routes, each passing its respective starting point, that together see all the treasures while minimizing the length of the longest of the routes.

While theoretical computer science primarily works with discrete models of computation, like the Turing machine and the wordRAM, there are many scenarios in which introducing real computation models is more adequate. For example, when working with continuous probability distributions for say smoothed analysis, in continuous optimization, computational geometry or machine learning. Furthermore, there are various problems earlier known to be NP-hard that have been found to be ER-complete. We want to investigate the relation between real models of computation with discrete models of computation. We do this by means of oracle separation results. In this paper, we define the notion of a real Turing machine as an extension of the (binary) Turing machine by adding a real tape. On this real tape, each memory cell can hold a real number. (This is equivalent to BSS-machines.) Using those machines, we define and study the real polynomial hierarchy RPH. We say that a language L subseteq {0,1}^* is in RPH if there is a constant k <= 1, a polynomial q, polynomial-time real Turing machine M, and (alternating) quantifiers Q_i in {exists, forall} such that x in L iff Q_1 u_1 in R^{q(|x|)} Q_2 u_2 in R^{q(|x|)} cdots Q_k u_k in R^{q(|x|)} M(x, u_1,ldots,u_k)=1. We refer to this as the real polynomial hierarchy, as the language L is binary, but we quantify over real numbers. The kth level of the hierarchy is denoted by SRPHlevel{k}, and PRPHlevel{k} respectively, depending on whether the first quantifier is existential or universal. We are interested in RPH as the first level of the hierarchy corresponds to the well-known complexity class ER. It is known that NP subseteq ER subseteq PSPACE and furthermore PH subseteq RPH subseteq PSPACE. We are interested to know if any of those inclusions are tight. In the absence of unconditional separations of complexity classes, we turn our attention to oracle separation. Oracle machines can ask questions of the form x in O for some oracle O. We develop a technique that allows us to transform oracle separation results from the classical binary world to the real world. As an application of our technique, we show that there are oracles such that: - RPH^O proper subset of PSPACE^O, - SPHlevel{k+1}^O not contained in SRPHlevel{k}^O, for all kgeq 0, - SRPHlevel{k}^O proper subset of SRPHlevel{k+1}^O, for all kgeq 0, - BQP^O not contained in RPH^O. Our results indicate that ER is strictly less powerful than PSPACE and that there is a separation between the different levels of the real polynomial hierarchy. Additionally, we bound the power of real computations by showing that NP-hard problems are not likely to be solvable using polynomial time on a realRAM. Furthermore, our oracle separations indicate that polynomial-time quantum computing cannot be simulated on a real Turing machine.

We consider what we denote the Boundary Visibility Partition Problem (Boundary-VPP) of finding generating points in an $n$ vertex simple polygon $\mathcal{P}$ that induce a set of visibility polygons partitioning the boundary of $\mathcal{P}$ into pairwise interior-disjoint segments. In particular, we require that every point on the boundary of $\mathcal{P}$ either belongs to exactly one visibility polygon, or alternatively, is a common vertex point for all visibility polygons that contain it. Assuming the Exponential Time Hypothesis (ETH), and assuming the real RAM model of computation for operations involving geometric primitives (e.g., coordinates for vertices or generating points), we rule out a $2^{o\left( n \cdot \left(\ln (\ln (n)) \cdot \ln \left(\frac{n}{\ln (\ln (n))}\right)\right)^{-1} \right)}$ time algorithm for the Boundary-VPP with rational inputs.

We consider the Shortest Descending Path (SDP) problem: computing a shortest path between two points on a polyhedral terrain that never increases in the z coordinate. No exact polynomial time algorithm is known for this problem. We show that SDPs are not computable within the ACMQ model, even for terrains with only three triangles. This confirms that the difficulty of the problem is mainly algebraic. We also identify a family of SDPs that can be computed exactly, unifying all previously known solvable terrain classes.

An obstacle representation of a graph G is constructed by drawing vertices at distinct points in the plane and by choosing a set of connected regions (the obstacles) such that G is the visibility graph of those points with respect to the obstacles. The convex obstacle number of G is the smallest number of convex obstacles that make it possible to construct an obstacle representation of G. It is known that every outerplanar graph has convex obstacle number five and that the convex obstacle number is at least four for some trees. In this paper we study the planar convex obstacle number of trees, that is the smallest number of convex obstacles that are needed to construct a crossing-free obstacle representation of a tree. We show that this number is Θ(n) for n-vertex trees by proving that (n-1)/4 convex obstacles are necessary even for some structurally simple trees, while n-1 unit disks are sufficient to construct a crossing-free obstacle representation of any tree.

Hyperbolic tilings are natural infinite planar graphs where each vertex has degree q and each face has p edges for some 1/p + 1/q < 1/2. We study the structure of shortest paths in such graphs. We show that given a set of n terminals, we can compute a so-called isometric closure (closely related to the geodesic convex hull) of the terminals in near-linear time, using a classic geometric convex hull algorithm as a black box. We show that the size of the convex hull is O(N) where N is the total length of the paths to the terminals from a fixed origin. Furthermore, we prove that the geodesic convex hull of a set of n terminals has treewidth only max(12, O(log(n/(p + q)))), a bound independent of the distance of the points involved. As a consequence, we obtain algorithms for subset TSP and Steiner tree with running time O(N log N) + poly(n/(p + q)) * N.

How to create a graph? How can we define a graph from a finite set of polygons or polylines? All we need is a binary relation which defines the edges. Natural examples are intersection, touching, contact and visibility. While intersection, touching, and contact graphs have been investigated before, visibility graphs have been studied only in restricted settings. We fill this gap by general visibility graphs, in which every vertex corresponds to a region, a polygon or a string (Jordan curve) in the plane and each edge corresponds to an unobstructed line of sight between any two points of the geometric objects corresponding to the connected vertices. General visibility graphs generalize point visibility graphs in which every vertex corresponds to a point. In this note, we establish fundamental properties of general visibility graphs and show that every hole-free map graph, which is a triangulated touching graph, is a general visibility graph.

The {p,q}-tiling graph is the (finite or infinite) planar graph T_{p,q} where all faces are cycles of length p and all vertices have degree q. We give algorithms for the problem of recognizing subgraphs and induced subgraphs of these tiling graphs, as follows. - For 1/p + 1/q > 1/2, these graphs correspond to the regular tilings of the sphere. These graphs are finite, thus recognizing their (induced) subgraphs can be done in constant time. - For 1/p + 1/q = 1/2, these graphs correspond to the regular tilings of the Euclidean plane. For the Euclidean square grid T_{4,4} Bhatt and Cosmadakis (IPL 1987) showed that recognizing subgraphs is NP-hard, even if the input graph is a tree. We show that a simple divide-and conquer algorithm achieves a subexponential running time in all Euclidean tilings, and we observe that there is an almost matching lower bound in T_{4,4} under the Exponential Time Hypothesis via known reductions. - For 1/p + 1/q < 1/2, these graphs correspond to the regular tilings of the hyperbolic plane. As our main contribution, we show that deciding if an n-vertex graph is isomorphic to a subgraph (or an induced subgraph) of the tiling T_{p,q} can be done in quasi-polynomial (n^{O(\log n)}) time for any fixed q. Our results for the hyperbolic case show that it has significantly lower complexity than the Euclidean variant, and it is unlikely to be NP-hard. The Euclidean results also suggest that the problem can be maximally hard even if the graph in question is a tree. Consequently, the known treewidth bounds for subgraphs of hyperbolic tilings do not lead to an efficient algorithm by themselves. Instead, we use convex hulls within the tiling graph, which have several desirable properties in hyperbolic tilings. Our key technical insight is that planar subgraph isomorphism can be computed via a dynamic program that builds a (canonical) sphere cut decomposition of a solution subgraph's convex hull.

The weak visibility polygon of a line segment $s$ inside a simple polygon $P$, denoted by $V(s)$, is the region of the polygon that is visible from at least one point on $s$. Given its fundamental nature in computational geometry, several algorithms have been proposed to compute weak visibility polygons efficiently. In this work, we present an implementation of an optimal linear-time algorithm for computing the weak visibility polygon of a segment inside a triangulated simple polygon. Our implementation provides exact, robust geometric primitives and optimizations to handle large inputs with more than 18,000,000 vertices. We demonstrate two concrete applications: (1) construction of window partitions, a standard data structure in visibility algorithms, and (2) support for optimal minimum-link path queries between two points in a simple polygon, the latter serving as a direct use case of the former. Experimental results confirm that the end-to-end runtime scales linearly with the size of the polygon and is dominated by the cost of computing the triangulation, validating the practicality and scalability of the approach.

One of the most fundamental problems in tiling theory is the domino problem: given a set of tiles and tiling rules, decide if there exists a way to tile the plane. The problem is known to be undecidable in general. We prove that the domino problem is decidable for robust tilesets, i.e. tilesets that either cannot tile the plane or can by provably satisfying some particular invariant. We establish that several famous tilesets considered in the literature are robust. As a side effect of our work, we provide a sound, relatively complete method for proving that a tileset can tile the plane. Our analysis also provides explanations for the similarities between proofs in the literature for various tilesets, as well as of phenomena that have been observed experimentally in the systematic study of tilesets using computer-assisted methods.

Let $P$ and $Q$ be simple polygons with $n$~vertices each. We wish to compute triangulations of $P$ and~$Q$ that are combinatorially equivalent, if they exist. We consider two versions of the problem: if a triangulation of~$P$ is given, we can decide in~$\bigO(n\log n + nr)$ time if~$Q$ has a compatible triangulation, where~$r$ is the number of reflex vertices of~$Q$. If we are already given the correspondence between vertices of~$P$ and~$Q$ (but no triangulation), we can find compatible triangulations of~$P$ and~$Q$ in time~$\bigO(M(n))$, where $M(n)$ is the running time for multiplying two~$n\times n$ matrices.

In a graph tiling problem, we are given a small set of tile types with multiplicities, and are asked to place them in a container such that their sides match. Each tile has a partial drawing of a graph on it. We consider a variant in which the resulting graph is required to be connected, and focus on cases that involve turn tiles.

The Beer index of a set S is the probability that two points chosen uniformly independently in S will see each other, that is, the segment connecting the two points will be contained in S. Previously, it has been shown that a simply connected set of unit Lebesgue measure with Beer index β>0 contains a convex subset of measure Ω(β). Easy examples show that the simple connectivity assumption cannot be omitted: a general set may have Beer index equal to 1 and no convex subset of positive measure. However, in this paper we extend the above result to general sets as follows: we show that a set S of unit Lebesgue measure in the plane with Beer index β>0 contains the boundary of a triangle of measure Ω(β^9). Furthermore, if S is an open domain of unit measure with K holes, then it contains the boundary of a triangle of measure Ω(β/K) and a convex subset of measure Ω(β/K^2).

We say that a tile is σ-morphic if it tiles the plane in exactly ℵ0 many noncongruent ways, where two tilings are said to be congruent if there’s an isometry mapping one to the other. It is an unsolved problem of whether a σ-morphic tile exists in the plane. In this note we present a construction of a set of convex tiles that is σ-morphic. The result is interesting since all the constructions of σ-morphic sets of tiles that arise in the literature make use of bumps and nicks, which necessarily make the tiles non-convex. We construct our set by cleverly dividing the tiles of the set of tiles discovered by Schmitt into convex tiles so that they behave in the same manner.