Tetsuo Asano, Hisao Tamaki, Naoki Katoh, Takeshi Tokuyama
Voronoi diagram for a set of geometric objects is a partition of the plane (or space in higher dimensions) into disjoint regions each dominated by some given object under a predetermined criterion....
Empirical Study on Branchwidth and Branch Decomposition of Planar Graphs (2008)
Zhengbing Bian, Qian-ping Gu, Marjan Marzban, Hisao Tamaki, Yumi Yoshitake
Geometry © 1998 Springer-Verlag New York Inc. How to Cut Pseudoparabolas into Segments (2008)
Hisao Tamaki, Takeshi Tokuyama
Abstract. LetƔ be a collection of unbounded x-monotone Jordan arcs intersecting at most twice each other, which we call pseudoparabolas, since two axis parallel parabolas intersect at most twice. We...
The Structure and Number of Global Roundings of a Graph (2008)
Tetsuo Asano, Naoki Katoh, Hisao Tamaki, Takeshi Tokuyama
Given a connected weighted graph G =(V,E), we consider a hypergraph HG = (V,PG) corresponding to the set of all shortest paths in G. For a given real assignment a on V satisfying 0 ≤ a(v) ≤ 1, a...
Voronoi diagrams with respect to criteria on vision information (2008)
Asano, Tetsuo, Katoh, Naoki, Tamaki, Hisao, Tokuyama, Takeshi
Motion Planning for a Steering-Constrained Point Robot through Moderate Obstacles (2007)
Pankaj K. Agarwal, Prabhakar Raghavan, Hisao Tamaki
Most mobile robots use steering mechanisms to guide their motion. Such mechanisms have stops that constrain the rate at which the robot can change its direction. We study a point robot in the plane...
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki
We are given a connected, undirected graph G on n vertices. There is a mobile robot on one of the vertices; this vertex is labeled s. Each of several other vertices contains a single movable...
Matching algorithms are fast in sparse random graphs (2006)
Holger Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki
Abstract. We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every...
Matching algorithms are fast in sparse random graphs (2006)
Holger Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every non-maximum...
Matching Algorithms are Fast in Sparse Random Graphs (2006)
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on $n$ vertices, with high probability every non-maximum...
Matching Algorithms Are Fast in Sparse Random Graphs (2004)
Bast,Holger, Mehlhorn,Kurt, Schäfer,Guido, Tamaki,Hisao
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every nonmaximum...
Matching Algorithms Are Fast in Sparse Random Graphs (2004)
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao, Diekert, Volker, Habib, Michel
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every nonmaximum...
Matching Algorithms Are Fast in Sparse Random Graphs (2004)
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao, Diekert, Volker, Habib, Michel
We present an improved average case analysis of the maximum cardinality matching problem. We show that in a bipartite or general random graph on n vertices, with high probability every nonmaximum...
Spanning Trees Crossing Few Barriers (2003)
Asano, Tetsuo, De Berg, Mark, Cheong, Otfried, Guibas, Leonidas J., Snoeyink, Jack, Tamaki, Hisao
We consider the problem of finding low-cost spanning trees for sets of $n$ points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a...
Bast,Holger, Mehlhorn,Kurt, Schäfer,Guido, Tamaki,Hisao
We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node $s$ and a target set $T$ is specified and the goal is to...
Bast, Holger, Mehlhorn, Kurt, Schäfer, Guido, Tamaki, Hisao
We consider the single-source many-targets shortest-path (SSMTSP) problem in directed graphs with non-negative edge weights. A source node $s$ and a target set $T$ is specified and the goal is to...
Spanning Trees Crossing Few Barriers (2002)
Asano, Tetsuo, Berg, Mark De, Cheong, Otfried, Guibas, Leonidas J., Snoeyink, Jack, Tamaki, Hisao
Spanning Trees Crossing Few Barriers (Algorithm Engineering as a New Paradigm) (1999)
Asano, Tetsuo, Berg, Mark De, Cheong, Otfried, Guibas, Leonidas J., Snoeyink, Jack, Tamaki, Hisao
Spanning trees crossing few barriers (1999)
Tetsuo Asano, Mark Berg Cheong, Leonidas J. Guibas, Jack Snoeyink, Hisao Tamaki
We consider the problem of finding low-cost spanning trees for sets of n points in the plane, where the cost of a spanning tree is defined as the total number of intersections of tree edges with a...
Latent Semantic Indexing: A Probabilistic Analysis (1998)
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, S. Vempala, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
Latent Semantic Indexing: A Probabilistic Analysis (1998)
Christos Papadimitriou Computer, Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
Latent Semantic Indexing: A Probabilistic Analysis (1997)
Christos H. Papadimitriou, Prabhakar Raghavan, Hisao Tamaki, Santosh Vempala
Latent semantic indexing (LSI) is an information retrieval technique based on the spectral analysis of the term-document matrix, whose empirical success had heretofore been without rigorous...
Routing a Permutation in the Hypercube by Two Sets of Edge Disjoint Paths (1996)
Hisao Tamaki, Qian-ping Gu, Qian-ping Gu
this paper, we concentrate on the case where I = O = V (G) and hence in the above denition is a permutation. There has been a great deal of work on the rearrangeability of various networks [3, 6, 9,...
Noise-Tolerant Distribution-Free Learning of General Geometric Concepts (1996)
Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki
this paper. First, we give an algorithm to learn C
Noise-Tolerant Distribution-Free Learning of General Geometric Concepts (1996)
Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki
We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ! d for fixed d. More specifically, let T be any set of s halfspaces. Let x = (x1 ; : : : ; xd) be...
Noise-Tolerant Distribution-Free Learning of General Geometric Concepts (1996)
Nader H. Bshouty, Sally A. Goldman, H. David Mathias, Subhash Suri, Hisao Tamaki
We present an efficient algorithm for PAC-learning a very general class of geometric concepts over ! for fixed d. More specifically, let T be a set of s halfspaces. Let x = (x 1 ; : : : ; x d ) be an...
On the Fault Tolerance of the Butterfly (1994)
Anna R. Karlin, Greg Nelson, Hisao Tamaki
We study the robustness of the butterfly network against random static faults. Suppose that each edge of the butterfly is present independently of other edges with probability p. Our main result is...
Motion Planning on a Graph (1994)
Christos H. Papadimitriou, Prabhakar Raghavan, Madhu Sudan, Hisao Tamaki
We are given a connected, undirected graph G on n vertices. There is a mobile robot on one of the vertices; this vertex is labeled s. Each of several other vertices contains a single movable...