Zobrazeno 1 - 10
of 125
pro vyhledávání: '"Rote, Guenter"'
Autor:
Rote, Günter
It is undecidable whether the language recognized by a probabilistic finite automaton is empty. Several other undecidability results, in particular regarding problems about matrix products, are based on this important theorem. We present three proofs
Externí odkaz:
http://arxiv.org/abs/2405.03035
Grid peeling is the process of repeatedly removing the convex hull vertices of the grid-points that lie inside a given convex curve. It has been conjectured that, for a more and more refined grid, grid peeling converges to a continuous process, the a
Externí odkaz:
http://arxiv.org/abs/2402.15787
Autor:
Rote, Günter
We survey a few strengthenings and generalizations of the Combinatorial Nullstellensatz of Alon and the Schwartz-Zippel Lemma. These lemmas guarantee the existence of (a certain number of) nonzeros of a multivariate polynomial when the variables run
Externí odkaz:
http://arxiv.org/abs/2305.10900
Autor:
Arkin, Esther M., Efrat, Alon, Knauer, Christian, Mitchell, Joseph S. B., Polishchuk, Valentin, Rote, Guenter, Schlipf, Lena, Talvitie, Topi
31st International Symposium on Computational Geometry (SoCG 2015)
We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in or
We show how to preprocess a polygonal domain with a fixed starting point s in order to answer efficiently the following queries: Given a point q, how should one move from s in or
Externí odkaz:
http://hdl.handle.net/10150/614771
http://arizona.openrepository.com/arizona/handle/10150/614771
http://arizona.openrepository.com/arizona/handle/10150/614771
Autor:
Rastanawi, Laith, Rote, Günter
We classify the finite groups of orthogonal transformations in 4-space, and we study these groups from the viewpoint of their geometric action, using polar orbit polytopes. For one type of groups (the toroidal groups), we develop a new classification
Externí odkaz:
http://arxiv.org/abs/2205.04965
Autor:
de Nooijer, Phoebe, Terziadis, Soeren, Weinberger, Alexandra, Masárová, Zuzana, Mchedlidze, Tamara, Löffler, Maarten, Rote, Günter
A face in a curve arrangement is called popular if it is bounded by the same curve multiple times. Motivated by the automatic generation of curved nonogram puzzles, we investigate possibilities to eliminate the popular faces in an arrangement by inse
Externí odkaz:
http://arxiv.org/abs/2202.12175
In a hypergraph with vertex set $V$ and edge set $E$, a real-valued function $f: V \to [0, 1]$ is a fractional transversal if $\sum_{v\in e} f(v) \ge 1$ for every edge $e \in E$. Its size is $|f| := \sum_{v \in V} f(v)$, and the fractional transversa
Externí odkaz:
http://arxiv.org/abs/2105.03890
Publikováno v:
Discrete and Computational Geometry 68 (2022), 1049-1077
What is the maximum number of intersections of the boundaries of a simple $m$-gon and a simple $n$-gon, assuming general position? This is a basic question in combinatorial geometry, and the answer is easy if at least one of $m$ and $n$ is even: If b
Externí odkaz:
http://arxiv.org/abs/2002.05680
Publikováno v:
Advances in Geometry 23 (2023), 135-150
We discuss a PL analogue of Morse theory for PL manifolds. There are several notions of regular and critical points. A point is homologically regular if the homology does not change when passing through its level, it is strongly regular if the functi
Externí odkaz:
http://arxiv.org/abs/1912.05054
Publikováno v:
Algorithms 12(12):254 (2019)
In this work, we study the $d$-Hitting Set and Feedback Vertex Set problems through the paradigm of finding diverse collections of $r$ solutions of size at most $k$ each, which has recently been introduced to the field of parameterized complexity [Ba
Externí odkaz:
http://arxiv.org/abs/1911.05032