Yoshio Okamoto
Drawing (Complete) Binary Tanglegrams: Hardness, Approximation, Fixed-Parameter Tractability.
Fri, 09/17/2010 - 15:02 — SomNambulAuthors: Yoshio Okamoto, Kevin Buchin, Alexander Wolff, Rodrigo I. Silveira, Martin Nöllenburg, Maike Buchin, Jaroslaw Byrka
Subjects: Computational Geometry
AbstractA \emph{binary tanglegram} is a drawing of a pair of rooted binary trees
whose leaf sets are in one-to-one correspondence; matching leaves are connected
by inter-tree edges. For applications, for example, in phylogenetics, it is
essential that both trees are drawn without edge crossings and that the
inter-tree edges have as few crossings as possible. It is known that finding a
tanglegram with the minimum number of crossings is NP-hard and that the problem
is fixed-parameter tractable with respect to that number.Minimum and maximum against k lies.
Wed, 02/03/2010 - 16:01 — SomNambulAuthors: Jiří Matoušek, Yoshio Okamoto, Michael Hoffmann, Philipp Zumstein
Subjects: Data Structures and Algorithms
AbstractA neat 1972 result of Pohl asserts that [3n/2]-2 comparisons are sufficient,
and also necessary in the worst case, for finding both the minimum and the
maximum of an n-element totally ordered set. The set is accessed via an oracle
for pairwise comparisons. More recently, the problem has been studied in the
context of the Renyi-Ulam liar games, where the oracle may give up to k false
answers. For large k, an upper bound due to Aigner shows that (k+O(\sqrt{k}))n
comparisons suffice. We improve on this by providing an algorithm with at most
(k+1+C)n+O(k^3) comparisons for some constant C.Querying Two Boundary Points for Shortest Paths in a Polygonal Domain.
Mon, 11/30/2009 - 16:01 — SomNambulAuthors: Sang Won Bae, Yoshio Okamoto
Subjects: Computational Geometry
AbstractWe consider a variant of two-point Euclidean shortest path query problem:
given a polygonal domain, build a data structure for two-point shortest path
query, provided that query points always lie on the boundary of the domain. As
a main result, we show that a logarithmic-time query for shortest paths between
boundary points can be performed using O~ (n^5) preprocessing time and O(n^5)
space where n is the number of corners of the polygonal domain and the O~
notation suppresses the polylogarithmic factor.
User login
