Source author record

Greg Aloupis

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

ResearcherUnclaimed source record

Computational Geometry Computational Complexity Computer Science and Game Theory math.CO

Catalog footprint

Research overview

9works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2025arXiv

Noncrossing Longest Paths and Cycles

Edge crossings in geometric graphs are sometimes undesirable as they could lead to unwanted situations such as collisions in motion planning and inconsistency in VLSI layout. Short geometric structures such as shortest perfect matchings, shortest spanning trees, shortest spanning paths, and shortest spanning cycles on a given point set are inherently noncrossing. However, the longest such structures need not be noncrossing. In fact, it is intuitive to expect many edge crossings in various geometric graphs that are longest. Recently, Álvarez-Rebollar, Cravioto-Lagos, Marín, Solé-Pi, and Urrutia (Graphs and Combinatorics, 2024) constructed a set of points for which the longest perfect matching is noncrossing. They raised several challenging questions in this direction. In particular, they asked whether the longest spanning path, on any finite set of points in the plane, must have a pair of crossing edges. They also conjectured that the longest spanning cycle must have a pair of crossing edges. In this paper, we give a negative answer to the question and also refute the conjecture. We present a framework for constructing arbitrarily large point sets for which the longest perfect matchings, the longest spanning paths, and the longest spanning cycles are noncrossing.

preprint2015arXiv

Classic Nintendo Games are (Computationally) Hard

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokemon. Our results apply to generalized versions of Super Mario Bros. 1-3, The Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games; all Metroid games; and all Pokemon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.

preprint2014arXiv

Compatible Connectivity-Augmentation of Planar Disconnected Graphs

Motivated by applications to graph morphing, we consider the following \emph{compatible connectivity-augmentation problem}: We are given a labelled $n$ -vertex planar graph, $\mathcal{G}$ , that has $r\ge 2$ connected components, and $k\ge 2$ isomorphic planar straight-line drawings, $G_1,\ldots,G_k$ , of $\mathcal{G}$ . We wish to augment $\mathcal G$ by adding vertices and edges to make it connected in such a way that these vertices and edges can be added to $G_1,\ldots,G_k$ as points and straight-line segments, respectively, to obtain $k$ planar straight-line drawings isomorphic to the augmentation of $\mathcal G$ . We show that adding $Θ(nr^{1-1/k})$ edges and vertices to $\mathcal{G}$ is always sufficient and sometimes necessary to achieve this goal. The upper bound holds for all $r\in\{2,\ldots,n\}$ and $k\ge 2$ and is achievable by an algorithm whose running time is $O(nr^{1-1/k})$ for $k=O(1)$ and whose running time is $O(kn^2)$ for general values of $k$ . The lower bound holds for all $r\in\{2,\ldots,n/4\}$ and $k\ge 2$ .

preprint2014arXiv

Covering Folded Shapes

Can folding a piece of paper flat make it larger? We explore whether a shape $S$ must be scaled to cover a flat-folded copy of itself. We consider both single folds and arbitrary folds (continuous piecewise isometries $S\rightarrow R^2$ ). The underlying problem is motivated by computational origami, and is related to other covering and fixturing problems, such as Lebesgue's universal cover problem and force closure grasps. In addition to considering special shapes (squares, equilateral triangles, polygons and disks), we give upper and lower bounds on scale factors for single folds of convex objects and arbitrary folds of simply connected objects.

preprint2013arXiv

Bichromatic compatible matchings

For a set $R$ of $n$ red points and a set $B$ of $n$ blue points, a $BR$ -matching is a non-crossing geometric perfect matching where each segment has one endpoint in $B$ and one in $R$ . Two $BR$ -matchings are compatible if their union is also non-crossing. We prove that, for any two distinct $BR$ -matchings $M$ and $M'$ , there exists a sequence of $BR$ -matchings $M = M_1, ..., M_k = M'$ such that $M_{i-1}$ is compatible with $M_i$ . This implies the connectivity of the compatible bichromatic matching graph containing one node for each bichromatic matching and an edge joining each pair of compatible matchings, thereby answering the open problem posed by Aichholzer et al. in "Compatible matchings for bichromatic plane straight-line graphs"

preprint2013arXiv

Fitting Voronoi Diagrams to Planar Tesselations

Given a tesselation of the plane, defined by a planar straight-line graph $G$ , we want to find a minimal set $S$ of points in the plane, such that the Voronoi diagram associated with $S$ "fits" \ $G$ . This is the Generalized Inverse Voronoi Problem (GIVP), defined in \cite{Trin07} and rediscovered recently in \cite{Baner12}. Here we give an algorithm that solves this problem with a number of points that is linear in the size of $G$ , assuming that the smallest angle in $G$ is constant.

preprint2013arXiv

The Complexity of Order Type Isomorphism

The order type of a point set in $R^d$ maps each $(d{+}1)$ -tuple of points to its orientation (e.g., clockwise or counterclockwise in $R^2$ ). Two point sets $X$ and $Y$ have the same order type if there exists a mapping $f$ from $X$ to $Y$ for which every $(d{+}1)$ -tuple $(a_1,a_2,\ldots,a_{d+1})$ of $X$ and the corresponding tuple $(f(a_1),f(a_2),\ldots,f(a_{d+1}))$ in $Y$ have the same orientation. In this paper we investigate the complexity of determining whether two point sets have the same order type. We provide an $O(n^d)$ algorithm for this task, thereby improving upon the $O(n^{\lfloor{3d/2}\rfloor})$ algorithm of Goodman and Pollack (1983). The algorithm uses only order type queries and also works for abstract order types (or acyclic oriented matroids). Our algorithm is optimal, both in the abstract setting and for realizable points sets if the algorithm only uses order type queries.

preprint2012arXiv

Circle separability queries in logarithmic time

Let $P$ be a set of $n$ points in the plane. In this paper we study a new variant of the circular separability problem in which a point set $P$ is preprocessed so that one can quickly answer queries of the following form: Given a geometric object $Q$ , report the minimum circle containing $P$ and exluding $Q$ . Our data structure can be constructed in $O(n\log n)$ time using O(n) space, and can be used to answer the query when $Q$ is either a circle or a convex $m$ -gon in $O(\log n)$ or $O(\log n + \log m)$ time, respectively.

preprint2010arXiv

Blocking Coloured Point Sets

This paper studies problems related to visibility among points in the plane. A point $x$ \emph{blocks} two points $v$ and $w$ if $x$ is in the interior of the line segment $\bar{vw}$ . A set of points $P$ is \emph{ $k$ -blocked} if each point in $P$ is assigned one of $k$ colours, such that distinct points $v,w\in P$ are assigned the same colour if and only if some other point in $P$ blocks $v$ and $w$ . The focus of this paper is the conjecture that each $k$ -blocked set has bounded size (as a function of $k$ ). Results in the literature imply that every 2-blocked set has at most 3 points, and every 3-blocked set has at most 6 points. We prove that every 4-blocked set has at most 12 points, and that this bound is tight. In fact, we characterise all sets $\{n_1,n_2,n_3,n_4\}$ such that some 4-blocked set has exactly $n_i$ points in the $i$ -th colour class. Amongst other results, for infinitely many values of $k$ , we construct $k$ -blocked sets with $k^{1.79...}$ points.

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.

Greg Aloupis

Research overview

Is this your work?

9 publications

Noncrossing Longest Paths and Cycles

Classic Nintendo Games are (Computationally) Hard

Compatible Connectivity-Augmentation of Planar Disconnected Graphs

Covering Folded Shapes

Bichromatic compatible matchings

Fitting Voronoi Diagrams to Planar Tesselations

The Complexity of Order Type Isomorphism

Circle separability queries in logarithmic time

Blocking Coloured Point Sets

See the researcher in context

Building this map preview