Distance Trisector Curves in Regular Convex Distance Metrics (2008)
Given two points A and B in the plane, we are interested in separating them by two curves CA and CB such that CA is equidistant from A and CB, and CB is equidistant from B and CA. Such curves...
Linear-Space Algorithms for Distance Preserving Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2-dimensional Euclidean space so that for each edge the distance between their...
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....
A Linear-Space Algorithm for Distance Preserving Graph Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in d-dimensional Euclidean space for a constant d so that for each edge the distance between...
Inserting Points Uniformly at Every Instance (2008)
Sachio Teramoto, Tetsuo Asano, Benjamin Doerr, Naoki Katoh
Abstract. A problem of arranging n points as uniformly as possible, which is equivalent to that of packing n equal and non-overlapping circles in a unit square, is frequently asked. In this paper we...
Template Matrices for Perfect Phylogeny Haplotyping and Site Consistency (2008)
Tetsuo Asano, Francesc Rosselló, Gabriel Valiente
The problem of inferring haplotype phase from a population of genotypes has received much attention recently, especially on the light of current large-scale efforts to characterize populations in...
Linear-Space Algorithms for Distance Preserving Embedding ∗ (2008)
Tetsuo Asano, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Chang Shu, Michiel Smid, ...
The distance preserving graph embedding problem is to embed vertices of a given weighted graph into points in 2-dimensional Euclidean space so that for each edge the distance between their...
×�Ö�� × �Ø � Ò�����ÓÖ�ÓÓ � Ó � �Ú�ÖÝ ÔÓ�ÒØ Ï � ÓÒ� � ØÙÖ� Ø��Ø � � × ÒÓØ �ÜÔÖ�××��Ð � �Ý...
I. PREVIOUS BINARIZATION ALGORITHMS (2008)
Xuefeng Liang, Arijit Bishnu, Tetsuo Asano
Here, we review three previous works and compare these methods against ours.
A Combined Radial Basis Function Model for Fingerprint Distortion (2008)
Xuefeng Liang, Tetsuo Asano, Hui Zhang
Abstract. Most fingerprint recognition techniques are based on minutiae matching and have been well studied. However, this technology still suffers from problems associated with the handling of poor...
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...
Fingerprint Matching Using Minutia Polygons (2008)
Fingerprint distortion changes both the geometric position and orientation of minutiae, and leads to difficulties in establishing a match among multiple impressions acquired from the same finger. In...
Voronoi diagrams with respect to criteria on vision information (2008)
Asano, Tetsuo, Katoh, Naoki, Tamaki, Hisao, Tokuyama, Takeshi
Space-Efficient Algorithm for Image Rotation (2008)
ASANO, Tetsuo, BITOU, Shinnya, MOTOKI, Mitsuo, USUI, Nobuaki
This paper presents an algorithm for rotating a subimage in place without using any extra working array. Due to this constraint, we have to overwrite pixel values by interpolated values. Key ideas...
On the Weak mod m Representation of Boolean Functions (2007)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
one article at a time in L ATEX source form on the Internet. Pagination
d_1-Optimal Motion for a Rod (Extended Abstract) (2007)
T. Asano, Tetsuo Asano, David Kirkpatrick, Chee K. Yap
) Tetsuo Asano 1 , David Kirkpatrick 2 , and Chee K. Yap 3 1 Osaka Electro-Communication University, Japan, 2 University of British Columbia, Canada, 3 Courant Institute, New York University, USA...
Tetsuo Asano, Yasuyuki Kawamura
this paper we analyze the voting technique based on the Hough transform from a standpoint of computational complexity following a mathematical definition of a digital line component to be detected....
Tetsuo Asano, Desh Ranjan, Thomas Roos
Digital halftoning is a well-known technique in image processing to convert an image having several bits for brightness levels into a binary image consisting only of black and white dots. A great...
Optimal Approximation of Monotone Curves on a Grid (Extended Abstract) (2007)
T. Asano, N. Katoh, Tetsuo Asano, Naoki Katoh, Elena Lodi, Thomas Roos
) Tetsuo Asano 1 Naoki Katoh 2 Elena Lodi 3 Thomas Roos 4 1 Dept. of Applied Electronics, Osaka Electro-Communication Univ., Neyagawa, Osaka 572, Japan (asano@djinni.osakac.ac.jp) 2 Kobe University...
X is an optimal solution, d: X (2007)
Tetsuo Asano, David Kirkpatrick, Chee Yap
We introduce a technique for computing approximate solutions to optimization problems. If X is the set of feasible solutions, the standard goal of approximation algorithms is to compute x X that is...
Constructing Optimal Highways (2007)
Ahn, Hee-Kap, Alt, Helmut, Asano, Tetsuo, Bae, Sang Won, Brass, Peter, Cheong, Otfried, ...
For two points $p$ and $q$ in the plane, a straight line $h$, called a highway, and a real $v>1$, we define the \emph{travel time} (also known as the \emph{city distance}) from $p$ and $q$ to be the...
Inserting Points Uniformly at Every Instance (2006)
TERAMOTO, Sachio, ASANO, Tetsuo, KATOH, Naoki, DOERR, Benjamin
Arranging n points as uniformly as possible is a frequently occurring problem. It is equivalent to packing n equal and non-overlapping circles in a unit square. In this paper we generalize this...
Computational Geometric and Combinatorial Approaches to (2006)
Digital Halftoning Tetsuo, Tetsuo Asano
This paper appeared at Computing: The Australasian Theory Symposium (CATS2006), Hobart, Australia. Conferences in Research and Practice in Information Technology (CRPIT), Vol. 51. Barry Jay and...
Inserting points uniformly at every instance (2006)
Teramoto, Sachio, Asano, Tetsuo, Katoh, Naoki, Doerr, Benjamin
Deterministic Random Walks on the Two-Dimensional Grid (2006)
Doerr, Benjamin, Friedrich, Tobias, Asano, Tetsuo
Deterministic and randomized balancing schemes are used to distribute workload evenly in networks. In this paper, we compare two very general ones: The random walk and the (deterministic) Propp...
Inserting Points Uniformly at Every Instance (2006)
Teramoto, Sachio, Asano, Tetsuo, Katoh, Naoki, Doerr, Benjamin
Arranging n points as uniformly as possible is a frequently occurring problem. It is equivalent to packing n equal and non-overlapping circles in a unit square. In this paper we generalize this...
Polyline Fitting of Planar Points under Min-sum Criteria (2006)
Aronov, Boris, Asano, Tetsuo, Katoh, Naoki, Mehlhorn, Kurt, Tokuyama, Takeshi
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
On Approximating the TSP with Intersecting Neighborhoods (2006)
Elbassioni, Khaled, Fishkin, Aleksei V., Sitters, Rene, Asano, Tetsuo
In the TSP with neighborhoods problem we are given a set of $n$ regions (neighborhoods) in the plane, and seek to find a minimum length TSP tour that goes through all the regions. We give two...
Doerr, Benjamin, Lengler, Johannes, Steurer, Daniel, Asano, Tetsuo
We regard the problem of communication in the presence of faulty transmissions. In contrast to the classical works in this area, we assume some structure on the times when the faults occur. More...
Approximation Scheme for Lowest Outdegree Orientation and Graph Density Measures (2006)
Kowalik, Lukasz, Asano, Tetsuo
We deal with the problem of finding such an orientation of a given graph that the largest number of edges leaving a vertex (called the outdegree of the orientation) is small. For any...
Polyline fitting of planar points under min-sum criteria (2006)
ARONOV, BORIS, ASANO, TETSUO, KATOH, NAOKI, MEHLHORN, KURT, TOKUYAMA, TAKESHI
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
A Linear Time Algorithm for Binary Fingerprint Image Denoising Using Distance Transform (2006)
Fingerprints are useful for biometric purposes because of their well known properties of distinctiveness and persistence over time. However, owing to skin conditions or incorrect finger pressure,...
Optimal Spanners for Axis-Aligned Rectangles (2005)
Asano, Tetsuo, De Berg, Mark, Cheong, Otfried, Everett, Hazel, Haverkort, Herman, Katoh, Naoki, ...
The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean...
Optimal spanners for axis-aligned rectangles (2005)
Alexander Wol, Tetsuo Asano, Tetsuo Asano, Mark De Berg, Mark De Berg, Otfried Cheong, ...
The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean...
Optimal spanners for axis-aligned rectangles (2005)
Tetsuo Asano, Mark Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, Naoki Katoh, ...
The dilation of a geometric graph is the maximum, over all pairs of points in the graph, of the ratio of the Euclidean length of the shortest path between them in the graph and their Euclidean...
Constructing Optimal Axis-Parallel Highways (2005)
Heekap Ahn, Tetsuo Asano, Sang Won Bae, Otfried Cheong, Chan-su Shin, Alexander Wolff
In this paper we consider the problem of constructing optimal highways. For two points p and q in the plane, a line h—the highway—and a real v> 1, we define the travel time (also known as the...
Polyline Fitting of Planar Points Under Min-sum Criteria (2004)
Aranov,Boris, Asano,Tetsuo, Katoh,Naoki, Mehlhorn,Kurt, Tokuyama,Takeshi
Polyline Fitting of Planar Points Under Min-sum Criteria (2004)
Aranov, Boris, Asano, Tetsuo, Katoh, Naoki, Mehlhorn, Kurt, Tokuyama, Takeshi, Fleischer, Rudolf, ...
A Generalization of Magic Squares with Applications to Digital Halftoning (2004)
Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. N, Shinji Sasahara, Takeaki Uno
Abstract. A semimagic square of order n is an n¢n matrix containing the integers 0�����n2 1 arranged in such a way that each row and column add up to the same value. We generalize this...
Optimal Spanners for Axis-Aligned Rectangles (2004)
Tetsuo Asano, Markk De Berg, Otfried Cheong, Hazel Everett, Herman Haverkort, Naoki Katoh, ...
this paper: we assume the topology of the network (the bridge graph) is given, and our only task is to place the bridges so as to minimize the dilation
A Generalization of Magic Squares with Applications to Digital Halftoning (2004)
Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. N, Shinji Sasahara, Takeaki Uno
Abstract. A semimagic square of order n is an n¢n matrix containing the integers 0�����n2 1 arranged in such a way that each row and column add up to the same value. We generalize this...
Polyline Fitting of Planar Points Under Min-sum Criteria (2004)
Aranov, Boris, Asano, Tetsuo, Katoh, Naoki, Mehlhorn, Kurt, Tokuyama, Takeshi, Fleischer, Rudolf, ...
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...
Tetsuo Asano, David Kirkpatrick, Chee K. Yap
We continue, and in a sense complete, our study the motion of a rod (line segment) in the plane in the presence of polygonal obstacles, under an optimality criterion based on minimizing the trace...
Spanning Trees Crossing Few Barriers (2002)
Asano, Tetsuo, Berg, Mark De, Cheong, Otfried, Guibas, Leonidas J., Snoeyink, Jack, Tamaki, Hisao
Asano, Tetsuo, Fujikawa, Naoki, Katoh, Naoki, Matsui, Tomomi, Nagamochi, Hiroshi, Tokuyama, Takeshi, ...
Minimum-Length Polygons In Approximation Sausages (2001)
Asano, Tetsuo, Kawamura, Yasuyuki, Obokata, Koji
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45...
A New Approximation Scheme for Digital Objects and Curve Length Estimations (2000)
Asano, Tetsuo, Kawamura, Yasuyuki, Obokata, Koji
You are granted permission for the non-commercial reproduction, distribution, display, and performance of this technical report in any format, BUT this permission is only for a period of 45...
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...
Okada, Akira, Iio, Satoshi, Asano, Tetsuo, Yoshimura, Masahiro
Boiling sulfuric acid was used to study the behavior of gas-pressure sintered silicon nitride with the additions of yttria and alumina. In the corrosion test ranging from 3 to 12 N for 1 h, the...
Corrosion Degradation Behavior of Alumina Ceramics in Hot Sulfuric Acid. (1998)
Asano, Tetsuo, Okada, Akira, Iio, Satoshi, Yoshimura, Masahiro
Corrosion behavior of 93 wt% alumina ceramics was investigated. The weight, the bending strength and the thickness of corroded layer were measured after exposed in sulfuric acid at temperatures of...
Polyline fitting of planar points under min-sum criteria (1998)
Boris Aronov, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
Polyline Fitting of Planar Points under Min-Sum (1998)
Criteria Boris Aronov, Boris Aronov, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama Polytechnic
Fitting a curve of a certain type to a given set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
Polyline Fitting of Planar Points under Min-Sum Criteria (1998)
Boris Aronov Tetsuo, Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, Takeshi Tokuyama
Fitting acurv e of a certain type to agiv en set of points in the plane is a basic problem in statistics and has numerous applications. We consider fitting a polyline with k joints under the min-sum...
Symmetric Logspace is Closed Under Complement (1995)
Noam Nisan, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 st connectivity problem to its complement. This shows that SL = coSL. 1 Introduction This paper deals with the complexity...
On the Weak mod m Representation of Boolean Functions (1995)
Vince Grolmusz, Abadi Greg, Frederickson John Mitchell, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, ...
Let P be a polynomial over the ring of mod m integers. P weakly represents Boolean function f : f0; 1g n ! f0; 1g if there is a subset S ` f0; 1; : : : ; m \Gamma 1g such that f(x) = 0 if and only if...
Probabilistically Checkable Debate Systems and Nonapproximability of PSPACE-Hard Functions (1995)
Pankaj Agarwal, Joan Feigenbaum, Carsten Lund, Andrew Goldberg, Ketan Mulmuley, ...
We initiate an investigation of probabilistically checkable debate systems (PCDS), a natural generalization of probabilistically checkable proof systems (PCPS). A PCDS for a language L consists of a...
Nils Klarlund, Dexter Kozen, Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, ...
Rabin conditions are a general class of properties of infinite sequences that encompass most known automata-theoretic acceptance conditions and notions of fairness. In this paper, we introduce a...
Symmetric Logspace is Closed under Complement (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
We present a Logspace, many-one reduction from the undirected Abstract-1 s--t connectivity problem to its complement. This shows that SL = coSL.
[ii] Chicago Journal of Theoretical Computer Science 1995-3Rabin Measures (1995)
Pankaj Agarwal, Andrew Goldberg, Ketan Mulmuley, Eric Allender, Georg Gottlob, Gil Neiger, ...
Published one article at a time in LATEX source form on the Internet. Pagination
Separating Bi-Chromatic Points by Parallel Lines (1994)
Tetsuo Asano, John Hershberger, János Pach, Eduardo Sontag, Diane Souvaine, Subhash Suri
Given a 2-coloring of the vertices of a regular n-gon P , how many parallel lines are needed to separate the vertices into monochromatic subsets? We prove that bn=2c is a tight upper bound, and also...
Separating Bi-Chromatic Points by Parallel Lines (1990)
Tetsuo Asano, John Hershberger, János Pach, Eduardo Sontag, Diane Souvaine, Subhash Suri
Given a 2-coloring of the vertices of a regular n-gon P, how many parallel lines are needed to separate the vertices into monochromatic subsets? We prove that ⌊n/2 ⌋ is a tight upper bound, and...
On the Construction of Abstract Voronoi Diagrams, II (1990)
Klein, R., Mehlhorn, Kurt, Meiser, Stefan, Asano, Tetsuo, Ibaraki, Toshihide, Imai, Hiroshi, ...
Space Filling Curves and Their Use in the Design of Geometric Data Structures
Tetsuo Asano, Desh Ranjan, Thomas Roos, Emo Welzl, Peter Widmayer
. We are given a two-dimensional square grid of size N \Theta N , where N := 2 n and n 0. A space filling curve (SFC) is a numbering of the cells of this grid with numbers from c + 1 to c +N 2 , for...