5 citations · 9 across the 12 of their papers we have counts for
18 papers
Drawings of Complete Multipartite Graphs Up to Triangle Flips
Oswin Aichholzer, Man-Kwun Chiu, Hung P. Hoang +5
For a drawing of a labeled graph, the rotation of a vertex or crossing is the cyclic order of its incident edges, represented by the labels of their other endpoints. The extended r…
Coloring circle arrangements: New -chromatic planar graphs
Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher +3
Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most . Motivated by this conjecture, we…
Snipperclips: Cutting Tools into Desired Polygons using Themselves
Zachary Abel, Hugo Akitaya, Man-Kwun Chiu +7
We study Snipperclips, a computer puzzle game whose objective is to create a target shape with two tools. The tools start as constant-complexity shapes, and each tool can snip (i.e…
Recognizing embedded caterpillars with weak unit disk contact representations is NP-hard
Man-Kwun Chiu, Jonas Cleve, Martin Nöllenburg
Weak unit disk contact graphs are graphs that admit a representation of the nodes as a collection of internally disjoint unit disks whose boundaries touch if there is an edge betwe…
New Results in Sona Drawing: Hardness and TSP Separation
Man-Kwun Chiu, Erik D. Demaine, Jenny Diomidova +6
Given a set of point sites, a sona drawing is a single closed curve, disjoint from the sites and intersecting itself only in simple crossings, so that each bounded region of its co…
Distance bounds for high dimensional consistent digital rays and 2-D partially-consistent digital rays
Man-Kwun Chiu, Matias Korman, Martin Suderland +1
We consider the problem of digitalizing Euclidean segments. Specifically, we look for a constructive method to connect any two points in . The construction must be {\…
Computational Complexity of the -Ham-Sandwich Problem
Man-Kwun Chiu, Aruni Choudhary, Wolfgang Mulzer
The classic Ham-Sandwich theorem states that for any measurable sets in , there is a hyperplane that bisects them simultaneously. An extension by Bárány, Hubard,…
A Generalization of Self-Improving Algorithms
Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin +1
Ailon et al. [SICOMP'11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances follow some unknown \emph{product…
On the Average Complexity of the -Level
Man-Kwun Chiu, Stefan Felsner, Manfred Scheucher +3
Let be an arrangement of lines in the Euclidean plane. The \emph{-level} of consists of all vertices of the arrangement which have exactly line…
Implicit Manifold Reconstruction
Siu-Wing Cheng, Man-Kwun Chiu
Let be a compact, smooth and boundaryless manifold with dimension and unit reach. We show how to construct a function $φ: \mathbb{R}^d \rightarr…
The Number of Convex Polyominoes with Given Height and Width
Kevin Buchin, Man-Kwun Chiu, Stefan Felsner +2
We give a new combinatorial proof for the number of convex polyominoes whose minimum enclosing rectangle has given dimensions. We also count the subclass of these polyominoes that…
Routing in Histograms
Man-Kwun Chiu, Jonas Cleve, Katharina Klost +5
Let be an -monotone orthogonal polygon with vertices. We call a simple histogram if its upper boundary is a single edge; and a double histogram if it has a horizonta…
A note on self-improving sorting with hidden partitions
Siu-Wing Cheng, Man-Kwun Chiu, Kai Jin
We study self-improving sorting with hidden partitions. Our result is an optimal algorithm which runs in expected time O(H(π(I)) + n), where I is the given input which contains n e…
Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain
Elena Arseneva, Man-Kwun Chiu, Matias Korman +5
We study the computation of the diameter and radius under the rectilinear link distance within a rectilinear polygonal domain of vertices and holes. We introduce a \emph{gr…
Balanced Line Separators of Unit Disk Graphs
Paz Carmi, Man Kwun Chiu, Matthew J. Katz +6
We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of unit disks in the plane there exists a line such that $\…
Routing in Polygonal Domains
Bahareh Banyassady, Man-Kwun Chiu, Matias Korman +7
We consider the problem of routing a data packet through the visibility graph of a polygonal domain with vertices and holes. We may preprocess to obtain a label and…
High Dimensional Consistent Digital Segments
Man-Kwun Chiu, Matias Korman
We consider the problem of digitalizing Euclidean line segments from to . Christ {\em et al.} (DCG, 2012) showed how to construct a set of {\em consist…
Hanabi is NP-hard, Even for Cheaters who Look at Their Cards
Jean-Francois Baffier, Man-Kwun Chiu, Yago Diez +5
In this paper we study a cooperative card game called Hanabi from the viewpoint of algorithmic combinatorial game theory. In Hanabi, each card has one among colors and a number…