Takeshi Tokuyama

Prof. Dr. Takeshi Tokuyama

Graduate School of Information Sciences (GSIS), Tohoku University, Aramaki Aza-Aoba, Aoba, Sendai 980-8579, Japan

Research Focus & Metrics

Academic Career Length

37Years (1990-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
7 March 2008 in Theoretical Computer Science
Verified
Journal Article
Closed access
PDF file
MHMagnús M. Halldórsson
Magnús M. Halldórsson
TTTakeshi Tokuyama
Takeshi Tokuyama

22 April 2009 in Discrete & Computational Geometry
Verified
Journal Article
Closed access
PDF file
JCJinhee Chun
Jinhee Chun
MKMatias Korman
Matias Korman
MNMartin Nöllenburg
Martin Nöllenburg
TTTakeshi Tokuyama
Takeshi Tokuyama

1 March 2003 in Algorithmica
Verified
Journal Article
Closed access
PDF file
HTHisao Tamaki
Hisao Tamaki
TTTakeshi Tokuyama
Takeshi Tokuyama

22 August 2016 in Algorithmica
Verified
Journal Article
Open access
PDF file
LGLeszek Gąsieniec
Leszek Gąsieniec
CLChristos Levcopoulos
Christos Levcopoulos
ALAndrzej Lingas
Andrzej Lingas
RPRasmus Pagh
Rasmus Pagh
TTTakeshi Tokuyama
Takeshi Tokuyama
We study the problem of efficiently correcting an erroneous product of two \(n\times n\) matrices over a ring. Among other things, we provide a randomized algorithm for correcting a matrix product with at most k erroneous entries running in \({\tilde{O}}(n^2+kn)\) time and a deterministic \({\tilde{O}}(kn^2)\)-time algorithm for this problem (where the notation \({\tilde{O}}\) suppresses polylogarithmic terms in n and k).

30 December 2005 in Algorithmica
Verified
Journal Article
Open access
PDF file
JCJinhee Chun
Jinhee Chun
KSKunihiko Sadakane
Kunihiko Sadakane
TTTakeshi Tokuyama
Takeshi Tokuyama
Given a function y = f(x) in one variable, we consider the problem of computing the single-peaked (unimodal) curve y =φ(x) minimizing the L2-distance between them. If the input function f is a histogram with O(n) steps or a piecewise linear function with O(n) linear pieces, we design algorithms for computing φ in linear time. We also give an algorithm to approximate f with a function consisting of the minimum number of unimodal pieces under the condition that each unimodal piece is within a fixed L2-distance from the corresponding portion of f.

1 January 1990
Verified
Conference Paper
Open access
PDF file
HAHiromi Aonuma
Hiromi Aonuma
HIHiroshi IMAI
Hiroshi IMAI
KIKeiko Imai
Keiko Imai
TTTakeshi Tokuyama
Takeshi Tokuyama
This paper considers the maximin placement of a convex polygon P inside a polygon Q, and introduce several new static and dynamic Voronoi diagrams to solve the problem. It is shown that P can be placed inside Q, using translation and rotation, so that the minimum Euclidean distance between any point on P and any point on Q is maximized in &Ogr;(m4n &lgr;16(mn) log mn) time, where m and n are the numbers of edges of P and Q, respectively, and &lgr;16(N) is the maximum length of Davenport-Schinzel sequences on N alphabets of order 16. If only translation is allowed, the problem can be solved in &Ogr;(mn log mn) time. The problem of placing multiple translates of P inside Q in a maximum manner is also considered, and in connection with this problem the dynamic Voronoi diagram of &kgr; rigidly moving sets of n points is investigated. The combinatorial complexity of this canonical dynamic diagram for &kgr;n points is shown to be &Ogr;(n2) and &Ogr;(n3&kgr;4 log* &kgr;) for &kgr; = 2, 3 and &kgr; ≥ 4, respectively. Several related problems are also treated in a unified way.