This list is also available as BibTeX.
Journal papers
-
Coloring circle arrangements: new 4-chromatic planar graphs
, , , , , and .Abstract: Felsner, Hurtado, Noy and Streinu (2000) conjectured that arrangement graphs of simple great-circle arrangements have chromatic number at most 3. Motivated by this conjecture, we study the colorability of arrangement graphs for different classes of (pseudo-)circle arrangements. In this paper the conjecture is verified for △-saturated pseudocircle arrangements, i.e., for arrangements where one color class of the 2-coloring of faces consists of triangles only, as well as for further classes of (pseudo-)circle arrangements. These results are complemented by a construction which maps △-saturated arrangements with a pentagonal face to arrangements with 4-chromatic 4-regular arrangement graphs. This corona construction has similarities with the crowning construction introduced by Koester (1985). Based on exhaustive experiments with small arrangements we propose three strengthenings of the original conjecture. We further investigate fractional colorings. It is shown that the arrangement graph of every arrangement A of pairwise intersecting pseudocircles is “close” to being 3-colorable. More precisely, the fractional chromatic number χf(A) of the arrangement graph is bounded from above by χf(A)≤3+O(1n), where n is the number of pseudocircles of A. Furthermore, we construct an infinite family of 4-edge-critical 4-regular planar graphs which are fractionally 3-colorable. This disproves a conjecture of Gimbel, Kündgen, Li, and Thomassen (2019).
European Journal of Combinatorics, page 103839, 2023.
@article{CHIU2023103839, author={Man-Kwun Chiu and Stefan Felsner and Manfred Scheucher and Felix Schröder and Raphael Steiner and Birgit Vogtenhuber}, title={Coloring circle arrangements: New 4-chromatic planar graphs}, journal={European Journal of Combinatorics}, year={2023}, pages={103839}, issn={0195-6698}, doi={https://doi.org/10.1016/j.ejc.2023.103839}, url={https://www.sciencedirect.com/science/article/pii/S0195669823001579} } -
A generalization of self-improving algorithms
, Siu-Wing Cheng, Man-Kwun Chiu, and .Abstract: Ailon et al. [SICOMP’11] proposed self-improving algorithms for sorting and Delaunay triangulation (DT) when the input instances x1, ... , xn follow some unknown product distribution. That is, xi is drawn independently from a fixed unknown distribution 𝒟i. After spending O(n1+ε) time in a learning phase, the subsequent expected running time is O((n + H)/ε), where H ∊ HS,HDT, and HS and HDT are the entropies of the distributions of the sorting and DT output, respectively. In this article, we allow dependence among the xi’s under the group product distribution. There is a hidden partition of [1, n] into groups; the xi’s in the kth group are fixed unknown functions of the same hidden variable uk; and the uk’s are drawn from an unknown product distribution. We describe self-improving algorithms for sorting and DT under this model when the functions that map uk to xi’s are well-behaved. After an O(poly(n))-time training phase, we achieve O(n + HS) and O(nα (n) + HDT) expected running times for sorting and DT, respectively, where α (⋅) is the inverse Ackermann function.
ACM Trans. Algorithms, 18(3), October 2022.
@article{10.1145/3531227, author={Jin, Kai and Cheng, Siu-Wing and Chiu, Man-Kwun and Wong, Man Ting}, title={A Generalization of Self-Improving Algorithms}, journal={ACM Trans. Algorithms}, year={2022}, volume={18}, number={3}, issn={1549-6325}, month={oct}, doi={10.1145/3531227}, url={https://doi.org/10.1145/3531227} } -
Distance bounds for high dimensional consistent digital rays and 2-d partially-consistent digital rays
Man-Kwun Chiu, Matias Korman, , and .
Discrete & Computational Geometry, 2022.
@article{chiu2021distance, author={Chiu, Man-Kwun and Korman, Matias and Martin Suderland and Takeshi Tokuyama}, title={Distance bounds for high dimensional consistent digital rays and 2-D partially-consistent digital rays}, journal={Discrete {\&} Computational Geometry}, year={2022}, doi={https://doi.org/10.1007/s00454-021-00349-6} } -
Snipperclips: cutting tools into desired polygons using themselves
, , Man-Kwun Chiu, , , , Matias Korman, , André van Renssen, and Marcel Roeloffzen.
Computational Geometry, 98:101784, 2021.
@article{DBLP:journals/comgeo/AbelACDDHKLRR21, author={Zachary Abel and Hugo A. Akitaya and Chiu, Man-Kwun and Erik D. Demaine and Martin L. Demaine and Adam Hesterberg and Korman, Matias and Jayson Lynch and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={Snipperclips: Cutting tools into desired polygons using themselves}, journal={Computational Geometry}, year={2021}, volume={98}, pages={101784}, doi={10.1016/j.comgeo.2021.101784}, url={https://doi.org/10.1016/j.comgeo.2021.101784} } -
Rectilinear link diameter and radius in a rectilinear polygonal domain
, Man-Kwun Chiu, Matias Korman, , , , André van Renssen, and Marcel Roeloffzen.
Computational Geometry, 92:101685, 2021.
@article{DBLP:journals/comgeo/ArsenevaCKMOORR21, author={Elena Arseneva and Chiu, Man-Kwun and Korman, Matias and Aleksandar Markovic and Yoshio Okamoto and Aur{\'{e}}lien Ooms and van Renssen, Andr\'e and Roeloffzen, Marcel}, title={Rectilinear link diameter and radius in a rectilinear polygonal domain}, journal={Computational Geometry}, year={2021}, volume={92}, pages={101685}, doi={10.1016/j.comgeo.2020.101685}, url={https://doi.org/10.1016/j.comgeo.2020.101685} } -
On the average complexity of the k-level
Man-Kwun Chiu, , , , , and .
Journal of Computational Geometry, 11(1):493–506, 2020.
@article{DBLP:journals/jocg/SteinerSFVCS20, author={Chiu, Man-Kwun and Stefan Felsner and Manfred Scheucher and Patrick Schnider and Raphael Steiner and Pavel Valtr}, title={On the Average Complexity of the k-Level}, journal={Journal of Computational Geometry}, year={2020}, volume={11}, number={1}, pages={493--506}, url={https://journals.carleton.ca/jocg/index.php/jocg/article/view/499} } -
Routing in polygonal domains
, Man-Kwun Chiu, Matias Korman, , André van Renssen, Marcel Roeloffzen, , , , and .Abstract: We consider the problem of routing a data packet through the visibility graph of a polygonal domain $P$ with $n$ vertices and $h$ holes. We may preprocess $P$ to obtain a label and a routing table for each vertex of $P$. Then, we must be able to route a data packet between any two vertices $p$ and $q$ of $P$, where each step must use only the label of the target node $q$ and the routing table of the current node. For any fixed $\epsilon>0$, we present a routing scheme that always achieves a routing path whose length exceeds the shortest path by a factor of at most $1+\epsilon$. The labels have $O(\log n)$ bits, and the routing tables are of size $O((\epsilon$$^{−1}+h)\log n)$. The preprocessing time is $O(n^2\log n)$. It can be improved to $O(n^2)$ for simple polygons.
Computational Geometry, 87:101593, 2020.
@article{DBLP:journals/comgeo/BanyassadyCKMRR20, author={Bahareh Banyassady and Chiu, Man-Kwun and Korman, Matias and Wolfgang Mulzer and van Renssen, Andr\'e and Roeloffzen, Marcel and Paul Seiferth and Yannik Stein and Birgit Vogtenhuber and Max Willert}, title={Routing in polygonal domains}, journal={Computational Geometry}, year={2020}, volume={87}, pages={101593}, doi={10.1016/j.comgeo.2019.101593}, url={https://doi.org/10.1016/j.comgeo.2019.101593} } -
Balanced line separators of unit disk graphs
, Man-Kwun Chiu, , Matias Korman, , André van Renssen, Marcel Roeloffzen, , and .Abstract: We prove a geometric version of the graph separator theorem for the unit disk intersection graph: for any set of $n$ unit disks in the plane there exists a line $\ell$ such that $\ell$ intersects at most $O((m+n)\log n)$ disks and each of the halfplanes determined by $\ell$ contains at most $2n/3$ unit disks from the set, where $m$ is the number of intersecting pairs of disks. We also show that an axis-parallel line intersecting $O(m+n)$ disks exists, but each halfplane may contain up to $4n/5$ disks. We give an almost tight lower bound (up to sublogarithmic factors) for our approach, and also show that no line-separator of sublinear size in $n$ exists when we look at disks of arbitrary radii, even when $m=0$. Proofs are constructive and suggest simple algorithms that run in linear time. Experimental evaluation has also been conducted, which shows that for random instances our method outperforms the method by Fox and Pach (whose separator has size $O(m)$).
Computational Geometry, 86, 2020.
@article{DBLP:journals/comgeo/CarmiCKKORRSS20, author={Paz Carmi and Chiu, Man-Kwun and Matthew J. Katz and Korman, Matias and Yoshio Okamoto and van Renssen, Andr\'e and Roeloffzen, Marcel and Taichi Shiitada and Shakhar Smorodinsky}, title={Balanced line separators of unit disk graphs}, journal={Computational Geometry}, year={2020}, volume={86}, doi={10.1016/j.comgeo.2019.101575}, url={https://doi.org/10.1016/j.comgeo.2019.101575} } -
Implicit manifold reconstruction
Siu-Wing Cheng and Man-Kwun Chiu.Abstract: Let $M \subset \mathbb{R}^d$ be a compact, smooth and boundaryless manifold with dimension $m$ and unit reach. We show how to construct a function $\varphi: \mathbb{R}^d \rightarrow \mathbb{R}$$^{d-m}$ from a uniform $(\epsilon,\kappa)$-sample $P$ of $\cal M$ that offers several guarantees. Let $Z_\varphi$ denote the zero set of $\varphi$. Let $\widehat{M}$ denote the set of points at distance $\epsilon$ or less from $\cal M$. There exists $\epsilon_0 \in (0,1)$ that decreases as $d$ increases such that if $\epsilon \leq \epsilon_0$, the following guarantees hold. First, $Z_\varphi \cap \widehat{M}$ is a faithful approximation of $\cal M$ in the sense that $Z_\varphi \cap \widehat{M}$ is homeomorphic to $\cal M$, the Hausdorff distance between $Z_\varphi \cap \widehat{M}$ and $\cal M$ is $O(m^{5/2}\epsilon^{2})$, and the normal spaces at nearby points in $Z_\varphi \cap \widehat{M}$ and $\cal M$ make an angle $O(m^2\sqrt{\kappa\epsilon})$. Second, $\varphi$ has local support; in particular, the value of $\varphi$ at a point is affected only by sample points in $P$ that lie within a distance of $O(m\epsilon)$. Third, we give a projection operator that only uses sample points in $P$ at distance $O(m\epsilon)$ from the initial point. The projection operator maps any initial point near $P$ onto $Z_\varphi \cap \widehat{M}$ in the limit by repeated applications.
Discrete & Computational Geometry, 62(3):700–742, Oct 2019.
@article{Cheng2019, author={Cheng, Siu-Wing and Chiu, Man-Kwun}, title={Implicit Manifold Reconstruction}, journal={Discrete {\&} Computational Geometry}, year={2019}, volume={62}, number={3}, pages={700--742}, issn={1432-0444}, month={Oct}, doi={10.1007/s00454-019-00095-w}, url={https://doi.org/10.1007/s00454-019-00095-w} } -
High dimensional consistent digital segments
Man-Kwun Chiu and Matias Korman.
SIAM Journal on Discrete Mathematics, 32(4):2566–2590, 2018.
@article{DBLP:journals/siamdm/ChiuK18, author={Chiu, Man-Kwun and Korman, Matias}, title={High Dimensional Consistent Digital Segments}, journal={SIAM Journal on Discrete Mathematics}, year={2018}, volume={32}, number={4}, pages={2566--2590}, doi={10.1137/17M1136572}, url={https://doi.org/10.1137/17M1136572} } -
Navigating weighted regions with scattered skinny tetrahedra
Siu-Wing Cheng, Man-Kwun Chiu, , and .
International Journal of Computational Geometry & Applications, 27(01n02):13–32, 2017.
@article{DBLP:jouranls/ijcga/ChengCJV17, author={Cheng, Siu-Wing and Chiu, Man-Kwun and Jiongxin Jin and Antoine Vigneron}, title={Navigating Weighted Regions with Scattered Skinny Tetrahedra}, journal={International Journal of Computational Geometry {\&} Applications}, year={2017}, volume={27}, number={01n02}, pages={13-32}, doi={10.1142/S0218195917600020}, url={http://www.worldscientific.com/doi/abs/10.1142/S0218195917600020} } -
Hanabi is NP-hard, even for cheaters who look at their cards
, Man-Kwun Chiu, , Matias Korman, , André van Renssen, Marcel Roeloffzen, and .Abstract: 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 $c$ colors and a number between $1$ and $n$. The aim is to make, for each color, a pile of cards of that color with all increasing numbers from $1$ to $n$. At each time during the game, each player holds $h$ cards in hand. Cards are drawn sequentially from a deck and the players should decide whether to play, discard or store them for future use. One of the features of the game is that the players can see their partners’ cards but not their own and information must be shared through hints. We introduce a single-player, perfect-information model and show that the game is intractable even for this simplified version where we forego both the hidden information and the multiplayer aspect of the game, even when the player can only hold two cards in her hand. On the positive side, we show that the decision version of the problem---to decide whether or not numbers from $1$ through $n$ can be played for every color---can be solved in (almost) linear time for some restricted cases.
Theoretical Computer Science, 675:43–55, 2017.
@article{BaffierCDKMRRU17, author={Baffier, Jean{-}Fran{\c{c}}ois and Chiu, Man-Kwun and Yago Diez and Korman, Matias and Valia Mitsou and van Renssen, Andr\'e and Roeloffzen, Marcel and Yushi Uno}, title={Hanabi is {NP}-hard, Even for Cheaters who Look at Their Cards}, journal={Theoretical Computer Science}, year={2017}, volume={675}, pages={43--55}, doi={10.1016/j.tcs.2017.02.024}, url={http://dx.doi.org/10.1016/j.tcs.2017.02.024} } -
Tangent estimation from point samples
Siu-Wing Cheng and Man-Kwun Chiu.
Discrete & Computational Geometry, 56(3):505–557, 2016.
@article{DBLP:journals/dcg/ChengC16, author={Cheng, Siu-Wing and Chiu, Man-Kwun}, title={Tangent Estimation from Point Samples}, journal={Discrete {\&} Computational Geometry}, year={2016}, volume={56}, number={3}, pages={505--557}, doi={10.1007/s00454-016-9809-z}, url={http://dx.doi.org/10.1007/s00454-016-9809-z} }
Conference papers
-
Drawings of complete multipartite graphs up to triangle flips
, Man-Kwun Chiu, , , , , , and .
Accepted to 39th International Symposium on Computational Geometry, SoCG 2023,.
@inproceedings{ACHHKMVW23, author={Oswin Aichholzer and Chiu, Man-Kwun and Hung P. Hoang and Michael Hoffmann and Jan Kyncl and Yannic Maus and Birgit Vogtenhuber and Alexandra Weinberger}, title={Drawings of Complete Multipartite Graphs Up to Triangle Flips}, booktitle={39th International Symposium on Computational Geometry, SoCG 2023,}, year={2023} } -
Coloring circle arrangements: new 4-chromatic planar graphs
Man-Kwun Chiu, , , , , and .
In Extended Abstracts EuroComb 2021, pages 84–91, 2021.
@inproceedings{CFSSSV21, author={Chiu, Man-Kwun and Stefan Felsner and Manfred Scheucher and Felix Schr{\"{o}}der and Raphael Steiner and Birgit Vogtenhuber}, title={Coloring Circle Arrangements: New 4-Chromatic Planar Graphs}, booktitle={Extended Abstracts EuroComb 2021}, year={2021}, publisher={Springer}, pages={84--91} } -
New results in sona drawing: hardness and tsp separation
Man-Kwun Chiu, , , , , , Matias Korman, , and .
In Proceedings of the 32nd Canadian Conference on Computational Geometry, (CCCG 2020), pages 63–72, 2020.
@inproceedings{CDDEHHKPR20, author={Chiu, Man-Kwun and Erik D. Demaine and Yevhenii Diomidov and David Eppstein and Robert A. Hearn and Adam Hesterberg and Korman, Matias and Irene Parada and Mikhail Rudoy}, title={New Results in Sona Drawing: Hardness and TSP Separation}, booktitle={Proceedings of the 32nd Canadian Conference on Computational Geometry, (CCCG 2020)}, year={2020}, pages={63--72} } -
Distance bounds for high dimensional consistent digital rays and 2-d partially-consistent digital rays
Man-Kwun Chiu, Matias Korman, , and .
In 28th Annual European Symposium on Algorithms (ESA 2020), pages 34:1–34:22, 2020.
@inproceedings{chiu2020distance, author={Chiu, Man-Kwun and Korman, Matias and Martin Suderland and Takeshi Tokuyama}, title={Distance bounds for high dimensional consistent digital rays and 2-D partially-consistent digital rays}, booktitle={28th Annual European Symposium on Algorithms (ESA 2020)}, year={2020}, volume={173}, pages={34:1--34:22} } -
Computational Complexity of the \(\alpha\)-Ham-Sandwich Problem
Man-Kwun Chiu, , and .
In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), pages 31:1–31:18, 2020.
@inproceedings{chiuCW20, author={Chiu, Man-Kwun and Aruni Choudhary and Wolfgang Mulzer}, title={Computational Complexity of the {\(\alpha\)}-Ham-Sandwich Problem}, booktitle={47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)}, year={2020}, editor={Artur Czumaj and Anuj Dawar and Emanuela Merelli}, publisher={Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik}, volume={168}, series={Leibniz International Proceedings in Informatics (LIPIcs)}, address={Dagstuhl, Germany}, pages={31:1--31:18}, isbn={978-3-95977-138-2}, doi={10.4230/LIPIcs.ICALP.2020.31}, url={https://drops.dagstuhl.de/opus/volltexte/2020/12438} } -
A generalization of self-improving algorithms
Siu-Wing Cheng, Man-Kwun Chiu, , and .
In 36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Zürich, Switzerland, pages 29:1–29:13, 2020.
@inproceedings{DBLP:conf/compgeom/ChengCJW20, author={Cheng, Siu-Wing and Chiu, Man-Kwun and Kai Jin and Man Ting Wong}, title={A Generalization of Self-Improving Algorithms}, booktitle={36th International Symposium on Computational Geometry, SoCG 2020, June 23-26, 2020, Z{\"{u}}rich, Switzerland}, year={2020}, editor={Sergio Cabello and Danny Z. Chen}, publisher={Schloss Dagstuhl - Leibniz-Zentrum f{\"{u}}r Informatik}, volume={164}, series={LIPIcs}, pages={29:1--29:13}, doi={10.4230/LIPIcs.SoCG.2020.29}, url={https://doi.org/10.4230/LIPIcs.SoCG.2020.29} } -
Routing in histograms
Man-Kwun Chiu, , , Matias Korman, , André van Renssen, Marcel Roeloffzen, and .
In Algorithms and Computation - 14th International Conference, WALCOM 2020, Singapore, March 31 - April 2, 2020, Proceedings, pages 43–54, 2020.
@inproceedings{DBLP:conf/walcom/ChiuCKKMRRW20, author={Chiu, Man-Kwun and Jonas Cleve and Katharina Klost and Korman, Matias and Wolfgang Mulzer and van Renssen, Andr\'e and Roeloffzen, Marcel and Max Willert}, title={Routing in Histograms}, booktitle={Algorithms and Computation - 14th International Conference, {WALCOM} 2020, Singapore, March 31 - April 2, 2020, Proceedings}, year={2020}, editor={M. Sohel Rahman and Kunihiko Sadakane and Wing{-}Kin Sung}, publisher={Springer}, volume={12049}, series={Lecture Notes in Computer Science}, pages={43--54}, doi={10.1007/978-3-030-39881-1_5}, url={https://doi.org/10.1007/978-3-030-39881-1_5} } -
Rectilinear link diameter and radius in a rectilinear polygonal domain
, Man-Kwun Chiu, Matias Korman, , , , , and .
In 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan, pages 58:1–58:13, 2018.
@inproceedings{DBLP:conf/isaac/ArsenevaCK0OORR18, author={Elena Arseneva and Chiu, Man-Kwun and Korman, Matias and Aleksandar Markovic and Yoshio Okamoto and Aur{\'{e}}lien Ooms and Andr{\'{e}} van Renssen and Marcel Roeloffzen}, title={Rectilinear Link Diameter and Radius in a Rectilinear Polygonal Domain}, booktitle={29th International Symposium on Algorithms and Computation, {ISAAC} 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan}, year={2018}, pages={58:1--58:13}, doi={10.4230/LIPIcs.ISAAC.2018.58}, url={https://doi.org/10.4230/LIPIcs.ISAAC.2018.58} } -
Routing in polygonal domains
, Man-Kwun Chiu, Matias Korman, , André van Renssen, Marcel Roeloffzen, , , , and .
In Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017), pages 10:1–10:13, 2017.
@inproceedings{DBLP:conf/isaac/BanyassadyCKMRR17, author={Bahareh Banyassady and Chiu, Man-Kwun and Korman, Matias and Wolfgang Mulzer and van Renssen, Andr\'e and Roeloffzen, Marcel and Paul Seiferth and Yannik Stein and Birgit Vogtenhuber and Max Willert}, title={Routing in Polygonal Domains}, booktitle={Proceedings of the 28th International Symposium on Algorithms and Computation (ISAAC 2017)}, year={2017}, pages={10:1--10:13}, doi={10.4230/LIPIcs.ISAAC.2017.10}, url={https://doi.org/10.4230/LIPIcs.ISAAC.2017.10} } -
Balanced line separators of unit disk graphs
, Man-Kwun Chiu, , Matias Korman, , André van Renssen, Marcel Roeloffzen, , and .
In Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017), pages 241–252, 2017.
@inproceedings{DBLP:conf/wads/CarmiCKKORRSS17, author={Paz Carmi and Chiu, Man-Kwun and Matthew J. Katz and Korman, Matias and Yoshio Okamoto and van Renssen, Andr\'e and Roeloffzen, Marcel and Taichi Shiitada and Shakhar Smorodinsky}, title={Balanced Line Separators of Unit Disk Graphs}, booktitle={Proceedings of the 15th Algorithms and Data Structures Symposium (WADS 2017)}, year={2017}, volume={10389}, series={Lecture Notes in Computer Science}, pages={241--252}, doi={10.1007/978-3-319-62127-2_21}, url={https://doi.org/10.1007/978-3-319-62127-2_21} } -
High dimensional consistent digital segments
Man-Kwun Chiu and Matias Korman.Abstract: We consider the problem of digitalizing Euclidean line segments from $\mathbb{R}^d$ to $\mathbb{Z}^d$. Christ et al. (DCG, 2012) showed how to construct a set of consistent digital segments (CDS) for $d=2$: a collection of segments connecting any two points in $\mathbb{Z}^2$ that satisfies the natural extension of the Euclidean axioms to $\mathbb{Z}^d$. In this paper we study the construction of CDSs in higher dimensions. We show that any total order can be used to create a set of consistent digital rays CDR in $\mathbb{Z}^d$ (a set of rays emanating from a fixed point $p$ that satisfies the extension of the Euclidean axioms). We fully characterize for which total orders the construction holds and study their Hausdorff distance, which in particular positively answers the question posed by Christ et al..
In 33rd International Symposium on Computational Geometry (SoCG 2017), pages 31:1–31:15, 2017.
@inproceedings{DBLP:conf/compgeom/ChiuK17, author={Chiu, Man-Kwun and Korman, Matias}, title={High Dimensional Consistent Digital Segments}, booktitle={33rd International Symposium on Computational Geometry (SoCG 2017)}, year={2017}, pages={31:1--31:15}, doi={10.4230/LIPIcs.SoCG.2017.31}, url={https://doi.org/10.4230/LIPIcs.SoCG.2017.31} } -
Hanabi is NP-complete, even for cheaters who look at their cards
, Man-Kwun Chiu, , Matias Korman, , André van Renssen, Marcel Roeloffzen, and .Abstract: This paper studies a cooperative card game called Hanabi from an algorithmic combinatorial game theory viewpoint. The aim of the game is to play cards from $1$ to $n$ in increasing order (this has to be done independently in $c$ different colors). Cards are drawn from a deck one by one. Drawn cards are either immediately played, discarded or stored for future use (overall each player can store up to $h$ cards). The main feature of the game is that players know the cards their partners hold (but not theirs. This information must be shared through hints). We introduce a simplified mathematical model of a single-player version of the game, and show several complexity results: the game is intractable in a general setting even if we forego with the hidden information aspect of the game. On the positive side, the game can be solved in linear time for some interesting restricted cases (i.e., for small values of $h$ and $c$).
In Proceedings of the 8th International Conference on Fun with Algorithms (FUN 2016), pages 4:1–4:17, 2016.
@inproceedings{DBLP:conf/fun/BaffierCDKMRRU16, author={Baffier, Jean{-}Fran{\c{c}}ois and Chiu, Man-Kwun and Yago Diez and Korman, Matias and Valia Mitsou and van Renssen, Andr\'e and Roeloffzen, Marcel and Yushi Uno}, title={Hanabi is {NP}-complete, Even for Cheaters who Look at Their Cards}, booktitle={Proceedings of the 8th International Conference on Fun with Algorithms ({FUN} 2016)}, year={2016}, pages={4:1--4:17}, doi={10.4230/LIPIcs.FUN.2016.4}, url={http://dx.doi.org/10.4230/LIPIcs.FUN.2016.4} } -
Navigating weighted regions with scattered skinny tetrahedra
Siu-Wing Cheng, Man-Kwun Chiu, , and .
In Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC 2015), pages 35–45, 2015.
@inproceedings{DBLP:conf/isaac/ChengCJV15, author={Cheng, Siu-Wing and Chiu, Man-Kwun and Jiongxin Jin and Antoine Vigneron}, title={Navigating Weighted Regions with Scattered Skinny Tetrahedra}, booktitle={Proceedings of the 26th International Symposium on Algorithms and Computation ({ISAAC} 2015)}, year={2015}, pages={35--45}, doi={10.1007/978-3-662-48971-0_4}, url={http://dx.doi.org/10.1007/978-3-662-48971-0_4} } -
Implicit manifold reconstruction
Siu-Wing Cheng and Man-Kwun Chiu.Abstract: Let $P$ be a dense set of points sampled from an $m$-dimensional compact smooth manifold $\Sigma$ in $\mathbb{R}^d$. We show how to construct an implicit function $\varphi: \mathbb{R}^d \rightarrow \mathbb{R}^d-m$ from $P$ so that the zero-set $S_\varphi$ of $\varphi$ contains a homeomorphic approximation of $\Sigma$. The Hausdorff distance between $\Sigma$ and this homeomorphic approximation is at most $\varepsilon^\tau$ for any fixed $\tau < 2$. Moreover, for every point $\mathsf{x}$ at distance $\varepsilon^\tau$ or less from $\Sigma$, the normal space of $S_\varphi$ at $\mathsf{x}$ makes an $O(\varepsilon^(\tau-1)/2)$ angle with the normal space of $\Sigma$ at the point nearest to $\mathsf{x}$. The function $\varphi$ has local support, which makes local homeomorphic reconstruction possible without a complete sampling.
In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014), pages 161–173, 2014.
@inproceedings{DBLP:conf/soda/ChengC14, author={Cheng, Siu-Wing and Chiu, Man-Kwun}, title={Implicit Manifold Reconstruction}, booktitle={Proceedings of the 25th Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA} 2014)}, year={2014}, pages={161--173}, doi={10.1137/1.9781611973402.12}, url={http://dx.doi.org/10.1137/1.9781611973402.12} } -
Dimension detection via slivers
Siu-Wing Cheng and Man-Kwun Chiu.
In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), pages 1001–1010, 2009.
@inproceedings{DBLP:conf/soda/ChengC09, author={Cheng, Siu-Wing and Chiu, Man-Kwun}, title={Dimension detection via slivers}, booktitle={Proceedings of the 20th Annual {ACM-SIAM} Symposium on Discrete Algorithms ({SODA} 2009)}, year={2009}, pages={1001--1010}, url={http://dl.acm.org/citation.cfm?id=1496770.1496879} }
Generated by Publy 1.1. Last modified on 4 March 2024.