Source author record

Thomas Hackl

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 Discrete Mathematics Data Structures and Algorithms math.MG

Catalog footprint

Research overview

13works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

A superlinear lower bound on the number of 5-holes

Let $P$ be a finite set of points in the plane in general position, that is, no three points of $P$ are on a common line. We say that a set $H$ of five points from $P$ is a $5$ -hole in $P$ if $H$ is the vertex set of a convex $5$ -gon containing no other points of $P$ . For a positive integer $n$ , let $h_5(n)$ be the minimum number of 5-holes among all sets of $n$ points in the plane in general position. Despite many efforts in the last 30 years, the best known asymptotic lower and upper bounds for $h_5(n)$ have been of order $Ω(n)$ and $O(n^2)$ , respectively. We show that $h_5(n) = Ω(n\log^{4/5}{n})$ , obtaining the first superlinear lower bound on $h_5(n)$ . The following structural result, which might be of independent interest, is a crucial step in the proof of this lower bound. If a finite set $P$ of points in the plane in general position is partitioned by a line $\ell$ into two subsets, each of size at least 5 and not in convex position, then $\ell$ intersects the convex hull of some 5-hole in $P$ . The proof of this result is computer-assisted.

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.

preprint2015arXiv

Representing Directed Trees as Straight Skeletons

The straight skeleton of a polygon is the geometric graph obtained by tracing the vertices during a mitered offsetting process. It is known that the straight skeleton of a simple polygon is a tree, and one can naturally derive directions on the edges of the tree from the propagation of the shrinking process. In this paper, we ask the reverse question: Given a tree with directed edges, can it be the straight skeleton of a polygon? And if so, can we find a suitable simple polygon? We answer these questions for all directed trees where the order of edges around each node is fixed.

preprint2014arXiv

Embedding Four-directional Paths on Convex Point Sets

A directed path whose edges are assigned labels "up", "down", "right", or "left" is called \emph{four-directional}, and \emph{three-directional} if at most three out of the four labels are used. A \emph{direction-consistent embedding} of an \mbox{ $n$ -vertex} four-directional path $P$ on a set $S$ of $n$ points in the plane is a straight-line drawing of $P$ where each vertex of $P$ is mapped to a distinct point of $S$ and every edge points to the direction specified by its label. We study planar direction-consistent embeddings of three- and four-directional paths and provide a complete picture of the problem for convex point sets.

preprint2014arXiv

Flips in combinatorial pointed pseudo-triangulations with face degree at most four

In this paper we consider the flip operation for combinatorial pointed pseudo-triangulations where faces have size 3 or 4, so-called combinatorial 4-PPTs. We show that every combinatorial 4-PPT is stretchable to a geometric pseudo-triangulation, which in general is not the case if faces may have size larger than 4. Moreover, we prove that the flip graph of combinatorial 4-PPTs is connected and has diameter $O(n^2)$ , even in the case of labeled vertices with fixed outer face. For this case we provide an $Ω(n\log n)$ lower bound.

preprint2014arXiv

Monotone Simultaneous Embedding of Directed Paths

We study monotone simultaneous embeddings of upward planar digraphs, which are simultaneous embeddings where the drawing of each digraph is upward planar, and the directions of the upwardness of different graphs can differ. We first consider the special case where each digraph is a directed path. In contrast to the known result that any two directed paths admit a monotone simultaneous embedding, there exist examples of three paths that do not admit such an embedding for any possible choice of directions of monotonicity. We prove that if a monotone simultaneous embedding of three paths exists then it also exists for any possible choice of directions of monotonicity. We provide a polynomial-time algorithm that, given three paths, decides whether a monotone simultaneous embedding exists and, in the case of existence, also constructs such an embedding. On the other hand, we show that already for three paths, any monotone simultaneous embedding might need a grid of exponential (w.r.t. the number of vertices) size. For more than three paths, we present a polynomial-time algorithm that, given any number of paths and predefined directions of monotonicity, decides whether the paths admit a monotone simultaneous embedding with respect to the given directions, including the construction of a solution if it exists. Further, we show several implications of our results on monotone simultaneous embeddings of general upward planar digraphs. Finally, we discuss complexity issues related to our problems.

preprint2014arXiv

On $k$ -Gons and $k$ -Holes in Point Sets

We consider a variation of the classical Erdős-Szekeres problems on the existence and number of convex $k$ -gons and $k$ -holes (empty $k$ -gons) in a set of $n$ points in the plane. Allowing the $k$ -gons to be non-convex, we show bounds and structural results on maximizing and minimizing their numbers. Most noteworthy, for any $k$ and sufficiently large $n$ , we give a quadratic lower bound for the number of $k$ -holes, and show that this number is maximized by sets in convex position.

preprint2013arXiv

Empty triangles in good drawings of the complete graph

A good drawing of a simple graph is a drawing on the sphere or, equivalently, in the plane in which vertices are drawn as distinct points, edges are drawn as Jordan arcs connecting their end vertices, and any pair of edges intersects at most once. In any good drawing, the edges of three pairwise connected vertices form a Jordan curve which we call a triangle. We say that a triangle is empty if one of the two connected components it induces does not contain any of the remaining vertices of the drawing of the graph. We show that the number of empty triangles in any good drawing of the complete graph $K_n$ with $n$ vertices is at least $n$ .

preprint2013arXiv

Geodesic-Preserving Polygon Simplification

Polygons are a paramount data structure in computational geometry. While the complexity of many algorithms on simple polygons or polygons with holes depends on the size of the input polygon, the intrinsic complexity of the problems these algorithms solve is often related to the reflex vertices of the polygon. In this paper, we give an easy-to-describe linear-time method to replace an input polygon $\mathcal{P}$ by a polygon $\mathcal{P}'$ such that (1) $\mathcal{P}'$ contains $\mathcal{P}$ , (2) $\mathcal{P}'$ has its reflex vertices at the same positions as $\mathcal{P}$ , and (3) the number of vertices of $\mathcal{P}'$ is linear in the number of reflex vertices. Since the solutions of numerous problems on polygons (including shortest paths, geodesic hulls, separating point sets, and Voronoi diagrams) are equivalent for both $\mathcal{P}$ and $\mathcal{P}'$ , our algorithm can be used as a preprocessing step for several algorithms and makes their running time dependent on the number of reflex vertices rather than on the size of $\mathcal{P}$ .

preprint2013arXiv

Linear transformation distance for bichromatic matchings

Let $P=B\cup R$ be a set of $2n$ points in general position, where $B$ is a set of $n$ blue points and $R$ a set of $n$ red points. A \emph{ $BR$ -matching} is a plane geometric perfect matching on $P$ such that each edge has one red endpoint and one blue endpoint. Two $BR$ -matchings are compatible if their union is also plane. The \emph{transformation graph of $BR$ -matchings} contains one node for each $BR$ -matching and an edge joining two such nodes if and only if the corresponding two $BR$ -matchings are compatible. In SoCG 2013 it has been shown by Aloupis, Barba, Langerman, and Souvaine that this transformation graph is always connected, but its diameter remained an open question. In this paper we provide an alternative proof for the connectivity of the transformation graph and prove an upper bound of $2n$ for its diameter, which is asymptotically tight.

preprint2012arXiv

Empty Monochromatic Simplices

Let $S$ be a $k$ -colored (finite) set of $n$ points in $\mathbb{R}^d$ , $d\geq 3$ , in general position, that is, no { $(d + 1)$ } points of $S$ lie in a common $(d - 1)$ }-dimensional hyperplane. We count the number of empty monochromatic $d$ -simplices determined by $S$ , that is, simplices which have only points from one color class of $S$ as vertices and no points of $S$ in their interior. For $3 \leq k \leq d$ we provide a lower bound of $Ω(n^{d-k+1+2^{-d}})$ and strengthen this to $Ω(n^{d-2/3})$ for $k=2$ . On the way we provide various results on triangulations of point sets in $\mathbb{R}^d$ . In particular, for any constant dimension $d\geq3$ , we prove that every set of $n$ points ( $n$ sufficiently large), in general position in $\mathbb{R}^d$ , admits a triangulation with at least $dn+Ω(\log n)$ simplices.

preprint2012arXiv

Flip Graphs of Degree-Bounded (Pseudo-)Triangulations

We study flip graphs of triangulations whose maximum vertex degree is bounded by a constant $k$ . In particular, we consider triangulations of sets of $n$ points in convex position in the plane and prove that their flip graph is connected if and only if $k > 6$ ; the diameter of the flip graph is $O(n^2)$ . We also show that, for general point sets, flip graphs of pointed pseudo-triangulations can be disconnected for $k \leq 9$ , and flip graphs of triangulations can be disconnected for any $k$ . Additionally, we consider a relaxed version of the original problem. We allow the violation of the degree bound $k$ by a small constant. Any two triangulations with maximum degree at most $k$ of a convex point set are connected in the flip graph by a path of length $O(n \log n)$ , where every intermediate triangulation has maximum degree at most $k+4$ .

preprint2009arXiv

Maximizing Maximal Angles for Plane Straight-Line Graphs

Let $G=(S, E)$ be a plane straight-line graph on a finite point set $S\subset\R^2$ in general position. The incident angles of a vertex $p \in S$ of $G$ are the angles between any two edges of $G$ that appear consecutively in the circular order of the edges incident to $p$ . A plane straight-line graph is called $ϕ$ -open if each vertex has an incident angle of size at least $ϕ$ . In this paper we study the following type of question: What is the maximum angle $ϕ$ such that for any finite set $S\subset\R^2$ of points in general position we can find a graph from a certain class of graphs on $S$ that is $ϕ$ -open? In particular, we consider the classes of triangulations, spanning trees, and paths on $S$ and give tight bounds in most cases.

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.

Thomas Hackl

Research overview

Is this your work?

13 publications

A superlinear lower bound on the number of 5-holes

Modem Illumination of Monotone Polygons

Representing Directed Trees as Straight Skeletons

Embedding Four-directional Paths on Convex Point Sets

Flips in combinatorial pointed pseudo-triangulations with face degree at most four

Monotone Simultaneous Embedding of Directed Paths

On $k$ -Gons and $k$ -Holes in Point Sets

Empty triangles in good drawings of the complete graph

Geodesic-Preserving Polygon Simplification

Linear transformation distance for bichromatic matchings

Empty Monochromatic Simplices

Flip Graphs of Degree-Bounded (Pseudo-)Triangulations

Maximizing Maximal Angles for Plane Straight-Line Graphs

See the researcher in context

Building this map preview

Thomas Hackl

Research overview

Is this your work?

13 publications

A superlinear lower bound on the number of 5-holes

Modem Illumination of Monotone Polygons

Representing Directed Trees as Straight Skeletons

Embedding Four-directional Paths on Convex Point Sets

Flips in combinatorial pointed pseudo-triangulations with face degree at most four

Monotone Simultaneous Embedding of Directed Paths

On kkk-Gons and kkk-Holes in Point Sets

Empty triangles in good drawings of the complete graph

Geodesic-Preserving Polygon Simplification

Linear transformation distance for bichromatic matchings

Empty Monochromatic Simplices

Flip Graphs of Degree-Bounded (Pseudo-)Triangulations

Maximizing Maximal Angles for Plane Straight-Line Graphs

See the researcher in context

Building this map preview

On $k$ -Gons and $k$ -Holes in Point Sets