This list is also available as BibTeX.
Journal papers
-
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
-
Computational complexity of the \(\alpha\)-ham-sandwich problem
Man-Kwun Chiu, , and .
In The 47th International Colloquium on Automata, Languages and Programming (ICALP 2020), 2020.
@inproceedings{chiuCW20, author={Chiu, Man-Kwun and Aruni Choudhary and Wolfgang Mulzer}, title={Computational Complexity of the {\(\alpha\)}-Ham-Sandwich Problem}, booktitle={The 47th International Colloquium on Automata, Languages and Programming (ICALP 2020)}, year={2020} } -
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 10 June 2020.