---
_id: '2159'
abstract:
- lang: eng
text: 'Motivated by topological Tverberg-type problems, we consider multiple (double,
triple, and higher multiplicity) selfintersection points of maps from finite simplicial
complexes (compact polyhedra) into ℝd and study conditions under which such multiple
points can be eliminated. The most classical case is that of embeddings (i.e.,
maps without double points) of a κ-dimensional complex K into ℝ2κ. For this problem,
the work of van Kampen, Shapiro, and Wu provides an efficiently testable necessary
condition for embeddability (namely, vanishing of the van Kampen ob-struction).
For κ ≥ 3, the condition is also sufficient, and yields a polynomial-time algorithm
for deciding embeddability: One starts with an arbitrary map f : K→ℝ2κ, which
generically has finitely many double points; if k ≥ 3 and if the obstruction vanishes
then one can successively remove these double points by local modifications of
the map f. One of the main tools is the famous Whitney trick that permits eliminating
pairs of double points of opposite intersection sign. We are interested in generalizing
this approach to intersection points of higher multiplicity. We call a point y
2 ℝd an r-fold Tverberg point of a map f : Kκ →ℝd if y lies in the intersection
f(σ1)∩. ∩f(σr) of the images of r pairwise disjoint simplices of K. The analogue
of (non-)embeddability that we study is the problem Tverbergκ r→d: Given a κ-dimensional
complex K, does it satisfy a Tverberg-type theorem with parameters r and d, i.e.,
does every map f : K κ → ℝd have an r-fold Tverberg point? Here, we show that
for fixed r, κ and d of the form d = rm and k = (r-1)m, m ≥ 3, there is a polynomial-time
algorithm for deciding this (based on the vanishing of a cohomological obstruction,
as in the case of embeddings). Our main tool is an r-fold analogue of the Whitney
trick: Given r pairwise disjoint simplices of K such that the intersection of
their images contains two r-fold Tverberg points y+ and y- of opposite intersection
sign, we can eliminate y+ and y- by a local isotopy of f. In a subsequent paper,
we plan to develop this further and present a generalization of the classical
Haeiger-Weber Theorem (which yields a necessary and sufficient condition for embeddability
of κ-complexes into ℝd for a wider range of dimensions) to intersection points
of higher multiplicity.'
acknowledgement: Swiss National Science Foundation (Project SNSF-PP00P2-138948)
author:
- first_name: Isaac
full_name: Mabillard, Isaac
id: 32BF9DAA-F248-11E8-B48F-1D18A9856A87
last_name: Mabillard
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Mabillard I, Wagner U. Eliminating Tverberg points, I. An analogue of the
Whitney trick. In: Proceedings of the Annual Symposium on Computational Geometry.
ACM; 2014:171-180. doi:10.1145/2582112.2582134'
apa: 'Mabillard, I., & Wagner, U. (2014). Eliminating Tverberg points, I. An
analogue of the Whitney trick. In Proceedings of the Annual Symposium on Computational
Geometry (pp. 171–180). Kyoto, Japan: ACM. https://doi.org/10.1145/2582112.2582134'
chicago: Mabillard, Isaac, and Uli Wagner. “Eliminating Tverberg Points, I. An Analogue
of the Whitney Trick.” In Proceedings of the Annual Symposium on Computational
Geometry, 171–80. ACM, 2014. https://doi.org/10.1145/2582112.2582134.
ieee: I. Mabillard and U. Wagner, “Eliminating Tverberg points, I. An analogue of
the Whitney trick,” in Proceedings of the Annual Symposium on Computational
Geometry, Kyoto, Japan, 2014, pp. 171–180.
ista: 'Mabillard I, Wagner U. 2014. Eliminating Tverberg points, I. An analogue
of the Whitney trick. Proceedings of the Annual Symposium on Computational Geometry.
SoCG: Symposium on Computational Geometry, 171–180.'
mla: Mabillard, Isaac, and Uli Wagner. “Eliminating Tverberg Points, I. An Analogue
of the Whitney Trick.” Proceedings of the Annual Symposium on Computational
Geometry, ACM, 2014, pp. 171–80, doi:10.1145/2582112.2582134.
short: I. Mabillard, U. Wagner, in:, Proceedings of the Annual Symposium on Computational
Geometry, ACM, 2014, pp. 171–180.
conference:
end_date: 2014-06-11
location: Kyoto, Japan
name: 'SoCG: Symposium on Computational Geometry'
start_date: 2014-06-08
date_created: 2018-12-11T11:56:03Z
date_published: 2014-06-08T00:00:00Z
date_updated: 2023-09-07T11:56:27Z
day: '08'
ddc:
- '510'
department:
- _id: UlWa
doi: 10.1145/2582112.2582134
file:
- access_level: open_access
checksum: 2aae223fee8ffeaf57bbabd8d92b6a2c
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:09:12Z
date_updated: 2020-07-14T12:45:30Z
file_id: '4735'
file_name: IST-2016-534-v1+1_Eliminating_Tverberg_points_I._An_analogue_of_the_Whitney_trick.pdf
file_size: 914396
relation: main_file
file_date_updated: 2020-07-14T12:45:30Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 171 - 180
publication: Proceedings of the Annual Symposium on Computational Geometry
publication_status: published
publisher: ACM
publist_id: '4847'
pubrep_id: '534'
quality_controlled: '1'
related_material:
record:
- id: '1123'
relation: dissertation_contains
status: public
scopus_import: 1
status: public
title: Eliminating Tverberg points, I. An analogue of the Whitney trick
type: conference
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2184'
abstract:
- lang: eng
text: 'Given topological spaces X,Y, a fundamental problem of algebraic topology
is understanding the structure of all continuous maps X→ Y. We consider a computational
version, where X,Y are given as finite simplicial complexes, and the goal is to
compute [X,Y], that is, all homotopy classes of suchmaps.We solve this problem
in the stable range, where for some d ≥ 2, we have dim X ≤ 2d-2 and Y is (d-1)-connected;
in particular, Y can be the d-dimensional sphere Sd. The algorithm combines classical
tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and
simplicial sets) with algorithmic tools from effective algebraic topology (locally
effective simplicial sets and objects with effective homology). In contrast, [X,Y]
is known to be uncomputable for general X,Y, since for X = S1 it includes a well
known undecidable problem: testing triviality of the fundamental group of Y. In
follow-up papers, the algorithm is shown to run in polynomial time for d fixed,
and extended to other problems, such as the extension problem, where we are given
a subspace A ⊂ X and a map A→ Y and ask whether it extends to a map X → Y, or
computing the Z2-index-everything in the stable range. Outside the stable range,
the extension problem is undecidable.'
acknowledgement: The research by M. K. was supported by project GAUK 49209. The research
by M. K. was also supported by project 1M0545 by the Ministry of Education of the
Czech Republic and by Center of Excellence { Inst. for Theor. Comput. Sci., Prague
(project P202/12/G061 of GACR). The research by U. W. was supported by the Swiss
National Science Foundation (SNF Projects 200021-125309, 200020-138230, and PP00P2-138948).
article_number: '17 '
author:
- first_name: Martin
full_name: Čadek, Martin
last_name: Čadek
- first_name: Marek
full_name: Krcál, Marek
id: 33E21118-F248-11E8-B48F-1D18A9856A87
last_name: Krcál
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Francis
full_name: Sergeraert, Francis
last_name: Sergeraert
- first_name: Lukáš
full_name: Vokřínek, Lukáš
last_name: Vokřínek
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing
all maps into a sphere. Journal of the ACM. 2014;61(3). doi:10.1145/2597629
apa: Čadek, M., Krcál, M., Matoušek, J., Sergeraert, F., Vokřínek, L., & Wagner,
U. (2014). Computing all maps into a sphere. Journal of the ACM. ACM. https://doi.org/10.1145/2597629
chicago: Čadek, Martin, Marek Krcál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek,
and Uli Wagner. “Computing All Maps into a Sphere.” Journal of the ACM.
ACM, 2014. https://doi.org/10.1145/2597629.
ieee: M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, and U. Wagner,
“Computing all maps into a sphere,” Journal of the ACM, vol. 61, no. 3.
ACM, 2014.
ista: Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. 2014. Computing
all maps into a sphere. Journal of the ACM. 61(3), 17.
mla: Čadek, Martin, et al. “Computing All Maps into a Sphere.” Journal of the
ACM, vol. 61, no. 3, 17, ACM, 2014, doi:10.1145/2597629.
short: M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, Journal
of the ACM 61 (2014).
date_created: 2018-12-11T11:56:12Z
date_published: 2014-05-01T00:00:00Z
date_updated: 2021-01-12T06:55:50Z
day: '01'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1145/2597629
intvolume: ' 61'
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1105.6257
month: '05'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '4797'
quality_controlled: '1'
scopus_import: 1
status: public
title: Computing all maps into a sphere
type: journal_article
user_id: 4435EBFC-F248-11E8-B48F-1D18A9856A87
volume: 61
year: '2014'
...
---
_id: '7038'
article_processing_charge: No
author:
- first_name: Kristóf
full_name: Huszár, Kristóf
id: 33C26278-F248-11E8-B48F-1D18A9856A87
last_name: Huszár
orcid: 0000-0002-5445-5057
- first_name: Michal
full_name: Rolinek, Michal
id: 3CB3BC06-F248-11E8-B48F-1D18A9856A87
last_name: Rolinek
citation:
ama: Huszár K, Rolinek M. Playful Math - An Introduction to Mathematical Games.
IST Austria
apa: Huszár, K., & Rolinek, M. (n.d.). Playful Math - An introduction to
mathematical games. IST Austria.
chicago: Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction
to Mathematical Games. IST Austria, n.d.
ieee: K. Huszár and M. Rolinek, Playful Math - An introduction to mathematical
games. IST Austria.
ista: Huszár K, Rolinek M. Playful Math - An introduction to mathematical games,
IST Austria, 5p.
mla: Huszár, Kristóf, and Michal Rolinek. Playful Math - An Introduction to Mathematical
Games. IST Austria.
short: K. Huszár, M. Rolinek, Playful Math - An Introduction to Mathematical Games,
IST Austria, n.d.
date_created: 2019-11-18T15:57:05Z
date_published: 2014-06-30T00:00:00Z
date_updated: 2020-07-14T23:11:45Z
day: '30'
ddc:
- '510'
department:
- _id: VlKo
- _id: UlWa
file:
- access_level: open_access
checksum: 2b94e5e1f4c3fe8ab89b12806276fb09
content_type: application/pdf
creator: dernst
date_created: 2019-11-18T15:57:51Z
date_updated: 2020-07-14T12:47:48Z
file_id: '7039'
file_name: 2014_Playful_Math_Huszar.pdf
file_size: 511233
relation: main_file
file_date_updated: 2020-07-14T12:47:48Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
page: '5'
publication_status: draft
publisher: IST Austria
status: public
title: Playful Math - An introduction to mathematical games
type: working_paper
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2014'
...
---
_id: '2807'
abstract:
- lang: eng
text: 'We consider several basic problems of algebraic topology, with connections
to combinatorial and geometric questions, from the point of view of computational
complexity. The extension problem asks, given topological spaces X; Y , a subspace
A ⊆ X, and a (continuous) map f : A → Y , whether f can be extended to a map X
→ Y . For computational purposes, we assume that X and Y are represented as finite
simplicial complexes, A is a subcomplex of X, and f is given as a simplicial map.
In this generality the problem is undecidable, as follows from Novikov''s result
from the 1950s on uncomputability of the fundamental group π1(Y ). We thus study
the problem under the assumption that, for some k ≥ 2, Y is (k - 1)-connected;
informally, this means that Y has \no holes up to dimension k-1" (a basic
example of such a Y is the sphere Sk). We prove that, on the one hand, this problem
is still undecidable for dimX = 2k. On the other hand, for every fixed k ≥ 2,
we obtain an algorithm that solves the extension problem in polynomial time assuming
Y (k - 1)-connected and dimX ≤ 2k - 1. For dimX ≤ 2k - 2, the algorithm also provides
a classification of all extensions up to homotopy (continuous deformation). This
relies on results of our SODA 2012 paper, and the main new ingredient is a machinery
of objects with polynomial-time homology, which is a polynomial-time analog of
objects with effective homology developed earlier by Sergeraert et al. We also
consider the computation of the higher homotopy groups πk(Y ), k ≥ 2, for a 1-connected
Y . Their computability was established by Brown in 1957; we show that πk(Y )
can be computed in polynomial time for every fixed k ≥ 2. On the other hand, Anick
proved in 1989 that computing πk(Y ) is #P-hard if k is a part of input, where
Y is a cell complex with certain rather compact encoding. We strengthen his result
to #P-hardness for Y given as a simplicial complex. '
author:
- first_name: Martin
full_name: Čadek, Martin
last_name: Čadek
- first_name: Marek
full_name: Krcál, Marek
id: 33E21118-F248-11E8-B48F-1D18A9856A87
last_name: Krcál
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Lukáš
full_name: Vokřínek, Lukáš
last_name: Vokřínek
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: 'Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. Extending continuous maps:
Polynomiality and undecidability. In: 45th Annual ACM Symposium on Theory of
Computing. ACM; 2013:595-604. doi:10.1145/2488608.2488683'
apa: 'Čadek, M., Krcál, M., Matoušek, J., Vokřínek, L., & Wagner, U. (2013).
Extending continuous maps: Polynomiality and undecidability. In 45th Annual
ACM Symposium on theory of computing (pp. 595–604). Palo Alto, CA, United
States: ACM. https://doi.org/10.1145/2488608.2488683'
chicago: 'Čadek, Martin, Marek Krcál, Jiří Matoušek, Lukáš Vokřínek, and Uli Wagner.
“Extending Continuous Maps: Polynomiality and Undecidability.” In 45th Annual
ACM Symposium on Theory of Computing, 595–604. ACM, 2013. https://doi.org/10.1145/2488608.2488683.'
ieee: 'M. Čadek, M. Krcál, J. Matoušek, L. Vokřínek, and U. Wagner, “Extending continuous
maps: Polynomiality and undecidability,” in 45th Annual ACM Symposium on theory
of computing, Palo Alto, CA, United States, 2013, pp. 595–604.'
ista: 'Čadek M, Krcál M, Matoušek J, Vokřínek L, Wagner U. 2013. Extending continuous
maps: Polynomiality and undecidability. 45th Annual ACM Symposium on theory of
computing. STOC: Symposium on the Theory of Computing, 595–604.'
mla: 'Čadek, Martin, et al. “Extending Continuous Maps: Polynomiality and Undecidability.”
45th Annual ACM Symposium on Theory of Computing, ACM, 2013, pp. 595–604,
doi:10.1145/2488608.2488683.'
short: M. Čadek, M. Krcál, J. Matoušek, L. Vokřínek, U. Wagner, in:, 45th Annual
ACM Symposium on Theory of Computing, ACM, 2013, pp. 595–604.
conference:
end_date: 2013-06-04
location: Palo Alto, CA, United States
name: 'STOC: Symposium on the Theory of Computing'
start_date: 2013-06-01
date_created: 2018-12-11T11:59:42Z
date_published: 2013-06-01T00:00:00Z
date_updated: 2021-01-12T06:59:51Z
day: '01'
ddc:
- '510'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1145/2488608.2488683
file:
- access_level: open_access
checksum: 06c2ce5c1135fbc1f71ca15eeb242dcf
content_type: application/pdf
creator: system
date_created: 2018-12-12T10:14:29Z
date_updated: 2020-07-14T12:45:48Z
file_id: '5081'
file_name: IST-2016-533-v1+1_Extending_continuous_maps_polynomiality_and_undecidability.pdf
file_size: 447945
relation: main_file
file_date_updated: 2020-07-14T12:45:48Z
has_accepted_license: '1'
language:
- iso: eng
month: '06'
oa: 1
oa_version: Submitted Version
page: 595 - 604
publication: 45th Annual ACM Symposium on theory of computing
publication_status: published
publisher: ACM
publist_id: '4078'
pubrep_id: '533'
quality_controlled: '1'
scopus_import: 1
status: public
title: 'Extending continuous maps: Polynomiality and undecidability'
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2013'
...
---
_id: '2244'
abstract:
- lang: eng
text: 'We consider two systems (α1,...,αm) and (β1,...,βn) of curves drawn on a
compact two-dimensional surface ℳ with boundary. Each αi and each βj is either
an arc meeting the boundary of ℳ at its two endpoints, or a closed curve. The
αi are pairwise disjoint except for possibly sharing endpoints, and similarly
for the βj. We want to "untangle" the βj from the αi by a self-homeomorphism
of ℳ; more precisely, we seek an homeomorphism φ: ℳ → ℳ fixing the boundary of
ℳ pointwise such that the total number of crossings of the αi with the φ(βj) is
as small as possible. This problem is motivated by an application in the algorithmic
theory of embeddings and 3-manifolds. We prove that if ℳ is planar, i.e., a sphere
with h ≥ 0 boundary components ("holes"), then O(mn) crossings can be
achieved (independently of h), which is asymptotically tight, as an easy lower
bound shows. In general, for an arbitrary (orientable or nonorientable) surface
ℳ with h holes and of (orientable or nonorientable) genus g ≥ 0, we obtain an
O((m + n)4) upper bound, again independent of h and g. '
acknowledgement: We would like to thank the authors of [GHR13] for mak- ing a draft
of their paper available to us, and, in particular, T. Huynh for an e-mail correspondence.
alternative_title:
- LNCS
arxiv: 1
author:
- first_name: Jiří
full_name: Matoušek, Jiří
last_name: Matoušek
- first_name: Eric
full_name: Sedgwick, Eric
last_name: Sedgwick
- first_name: Martin
full_name: Tancer, Martin
id: 38AC689C-F248-11E8-B48F-1D18A9856A87
last_name: Tancer
orcid: 0000-0002-1191-6714
- first_name: Uli
full_name: Wagner, Uli
id: 36690CA2-F248-11E8-B48F-1D18A9856A87
last_name: Wagner
orcid: 0000-0002-1494-0568
citation:
ama: Matoušek J, Sedgwick E, Tancer M, Wagner U. Untangling two systems of noncrossing
curves. 2013;8242:472-483. doi:10.1007/978-3-319-03841-4_41
apa: 'Matoušek, J., Sedgwick, E., Tancer, M., & Wagner, U. (2013). Untangling
two systems of noncrossing curves. Presented at the GD: Graph Drawing and Network
Visualization, Bordeaux, France: Springer. https://doi.org/10.1007/978-3-319-03841-4_41'
chicago: Matoušek, Jiří, Eric Sedgwick, Martin Tancer, and Uli Wagner. “Untangling
Two Systems of Noncrossing Curves.” Lecture Notes in Computer Science. Springer,
2013. https://doi.org/10.1007/978-3-319-03841-4_41.
ieee: J. Matoušek, E. Sedgwick, M. Tancer, and U. Wagner, “Untangling two systems
of noncrossing curves,” vol. 8242. Springer, pp. 472–483, 2013.
ista: Matoušek J, Sedgwick E, Tancer M, Wagner U. 2013. Untangling two systems of
noncrossing curves. 8242, 472–483.
mla: Matoušek, Jiří, et al. Untangling Two Systems of Noncrossing Curves.
Vol. 8242, Springer, 2013, pp. 472–83, doi:10.1007/978-3-319-03841-4_41.
short: J. Matoušek, E. Sedgwick, M. Tancer, U. Wagner, 8242 (2013) 472–483.
conference:
end_date: 2013-09-25
location: Bordeaux, France
name: 'GD: Graph Drawing and Network Visualization'
start_date: 2013-09-23
date_created: 2018-12-11T11:56:32Z
date_published: 2013-09-01T00:00:00Z
date_updated: 2023-02-21T17:03:07Z
day: '01'
department:
- _id: UlWa
doi: 10.1007/978-3-319-03841-4_41
external_id:
arxiv:
- '1302.6475'
intvolume: ' 8242'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: http://arxiv.org/abs/1302.6475
month: '09'
oa: 1
oa_version: Preprint
page: 472 - 483
project:
- _id: 25FA3206-B435-11E9-9278-68D0E5697425
grant_number: PP00P2_138948
name: 'Embeddings in Higher Dimensions: Algorithms and Combinatorics'
publication_status: published
publisher: Springer
publist_id: '4707'
quality_controlled: '1'
related_material:
record:
- id: '1411'
relation: later_version
status: public
scopus_import: 1
series_title: Lecture Notes in Computer Science
status: public
title: Untangling two systems of noncrossing curves
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 8242
year: '2013'
...