Zobrazeno 1 - 10
of 21
pro vyhledávání: '"Hsien-Chih Chang"'
Autor:
Hsien-Chih Chang, Arnaud de Mesmay
Publikováno v:
SODA
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, Jan 2020, Salt Lake City, United States. pp.747-766, ⟨10.1137/1.9781611975994.46⟩
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms
Proceedings of the 2020 ACM-SIAM Symposium on Discrete Algorithms, Jan 2020, Salt Lake City, United States. pp.747-766, ⟨10.1137/1.9781611975994.46⟩
We prove the first polynomial bound on the number of monotonic homotopy moves required to tighten a collection of closed curves on any compact orientable surface, where the number of crossings in the curve is not allowed to increase at any time durin
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::41de1f1757980058cba982b6e9bfc83c
https://doi.org/10.1145/3558097
https://doi.org/10.1145/3558097
Publikováno v:
ACM Transactions on Algorithms. 18:1-37
We investigate dynamic versions of geometric set cover and hitting set where points and ranges may be inserted or deleted, and we want to efficiently maintain an (approximately) optimal solution for the current problem instance. While their static ve
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7635d1d7c43af757c995e8807b77babb
https://doi.org/10.1145/3551639
https://doi.org/10.1145/3551639
Publikováno v:
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6c2734c9131f3d844850bd01c911b9dd
https://doi.org/10.1145/3519935.3519977
https://doi.org/10.1145/3519935.3519977
Publikováno v:
Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::eeb1a6301b2977af8f6cee1666f930ab
https://doi.org/10.1145/3519935.3519998
https://doi.org/10.1145/3519935.3519998
Autor:
Benjamin A. Burton, Hsien-Chih Chang, Maarten Löffler, Clément Maria, Arnaud de Mesmay, Saul Schleimer, Eric Sedgwick, Jonathan Spreer
We present three "hard" diagrams of the unknot. They require (at least) three extra crossings before they can be simplified to the trivial unknot diagram via Reidemeister moves in $\mathbb{S}^2$. Both examples are constructed by applying previously p
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::895c2831a3b913c861fa45b6497de8af
http://arxiv.org/abs/2104.14076
http://arxiv.org/abs/2104.14076
Publikováno v:
ACM Transactions on Algorithms; Nov2022, Vol. 18 Issue 4, p1-37, 37p
Autor:
Hsien-Chih Chang, Jeff Erickson
Publikováno v:
Discrete & Computational Geometry. 58:889-920
Any generic closed curve in the plane can be transformed into a simple closed curve by a finite sequence of local transformations called homotopy moves. We prove that simplifying a planar closed curve with $n$ self-crossings requires $\Theta(n^{3/2})
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::873d583136cf61dda1cff343b94c99cc
https://doi.org/10.1007/s00454-017-9907-6
https://doi.org/10.1007/s00454-017-9907-6
Autor:
Charles Carlson, Hsien-Chih Chang, Alexandra Kolla, Naonori Kakimura, Karthekeyan Chandrasekaran
The spectra of signed matrices have played a fundamental role in social sciences, graph theory, and control theory. In this work, we investigate the computational problems of finding symmetric signings of matrices with natural spectral properties. Ou
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1175311b0c764eaab2fb72d830d35494
Autor:
Saul Schleimer, Eric Sedgwick, Stephan Tillmann, David Letscher, Dylan P. Thurston, Hsien-Chih Chang, Arnaud de Mesmay, Jeff Erickson
Publikováno v:
SODA
ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States
ACM-SIAM Symposium on Discrete Algorithms
ACM-SIAM Symposium on Discrete Algorithms, Jan 2018, New Orleans, United States
We prove new upper and lower bounds on the number of homotopy moves required to tighten a closed curve on a compact orientable surface (with or without boundary) as much as possible. First, we prove that Ω(n2) moves are required in the worst case to
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::350b6f24f3130135774fad30fbf4c4bd
https://doi.org/10.1137/1.9781611975031.8
https://doi.org/10.1137/1.9781611975031.8