List of Publications

Tetsuo ASANO

Ph.D. Thesis (Doctor of Engineering)

"Wire Routing Scheme Based on Graph Theory Model"
Graduate School of Osaka University, School of Engineering Science, 1977.

[100] Tetsuo Asano and Revant Kumar, "A Small-Space Algorithm for Removing Small Connected Components from a Binary Image," to appear in IEICE Trans. EA, Special Section on Discrete Mathematics and Its Applications.

2012

[99] Tetsuo Asano, Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara: ``Kaboozle is NP-complete, even in a Strip Form,'' Journal of Information Processing, 20(3), pp. 713-718, 2012.

[98] Tetsuo Asano, Jesper Jansson, Kunihiko Sadakane, Ryuhei Uehara, and Gabriel Valiente: ``Faster Computation of the Robinson-Foulds Distance between Phylogenetic Networks,'' Information Sciences, Inf. Sci. 197: 77-90 (2012).

[97] T. Asano, ``In-place Algorithm for Erasing a Connected Component in a Binary Image,'' Theory of Computing Systems, 50, 1, pp. 111-123,2 2012.

2011

[96] Tetsuo Asano, Wolfgang Mulzer, and yajun Wang, ``Constant-Work-Space Algorithms for Shortest Paths in Trees and Simple Polygons,'' Journal of Graph Algorithms and Applications, Vol. 15, no. 5, pp. 569-586, 2011..

[95] Eishi Chiba, Tetsuo Asano, Takeshi Miura, Naoki Katoh and Ikuo Mitsuka, "Collision Probability in an In-Line Machines Model, Transactions on Computational Science XIII, LNCS 6750, pp. 1-12. Springer, Heidelberg (2011)

[94] T. Asano, W. Mulzer, G. Rote, Y. Wang,``Constant-work-space Algorithms for Geometric Problems,'' Journal of Computational Geometry, 2(1), pp:46-68, 2011.

[93] T. Asano, ``Constant-Work-Space Image Scan with a Given Angle,'' Interdisciplinary Information Sciences,Vol. 17 (2011) , No. 1 pp.39-44.

2010

[92] T. Asano and H. Tanaka, ``In-place Algorithm for Connected Components Labeling,'' Journal of Pattern Recognition Research, vol.5, No. 1, pp:10-22, 2010.

[91] T. Asano and H. Tanaka, ``In-place Linear-time Algorithms for Euclidean Distance Transform,'' LNCS Transactions on Computational Science, 8, pp:103-113, 2010.

[90] B. Aronov, T. Asano, and S. Funke, ``Optimal Triangulations of points and segments with steiner points,'' International Journal of Computational Geometry and Applications, 20, 1, pp:89-104, 2010.

[89] T. Asano, Peter Brass, and Shinji Sasahara, ``Disc Covering Problem with Application to Digital Halftoning,’’ Theory of Computing System, vol. 46, No.2, pp.157-173, February 2010.

2009

[88] T. Asano, V. E. Brimkov, R. P. Barneva: Some theoretical challenges in digital geometry: A perspective. Discrete Applied Mathematics, 157(16), pp: 3362-3371, 2009.

[87] Tetsuo Asano, Sergey Bereg, and David Kirkpatrick: “Finding Nearest Larger Neighbors: A Case Stgudy in Algorithm Design and Analysis,” Lecture Notes in Computer Science, “Efficient Algorithms,” editied by S. Albers, H. Alt, and S. Naeher, Springer, pp.249-260, 2009.

[86] Hee-Kap Ahn, Helmut Alt, Tetsuo Asano, Sang Won Bae, Peter Brass, Otfried Cheong, Christian Knauer, Hyeon-Suk Na, Chan-Su Shin, and Alexander Wolff, ``Constructing Optimal Highways,'' Internat. J. Found. Comput. Sci.,  20, 1, pp.3-23, 2009.

[85] Tetsuo Asano, Naoki Katoh, Kurt Mehlhorn, and Takeshi Tokuyama: “Some Generalizations of Least-Squares Algorithms,”  in Statistical Science and Interdiciplinary Research Vol.3, ``Algorithms, Architectures and Information Systems Security,'' edited by B.B. Bhattacharya, S. Sur-Kolay, S.C. Nandy, and A. BaguchiI,  World Scientific Publishers, pp.55-74, 2009.

[84] T. Asano, ``Constant-Working-Space Algorithms for Image Processing,'' Monograph: ``ETVC08: Emerging Trends and Challenges in Visual Computing，'' ETVC 2008: 268-283, edited by Frank Nielsen, 2009.

[83] T. Asano, P. Bose, P. Carmi, A. Maheshwari, C. Shu, M.. Smid, and S. Wuhrer, `` A Linear-Space Algorithm for Distance Preserving Graph Embedding,’’Computational Geometry: Theory and Applications, 42(4), pp.289-304,, 2009.

[82] Hee-Kap Ahn, Helmut Alt, Tetsuo Asano, Sang Won Bae, Peter Brass, Otfried Cheong, Christian Knauer, Hyeon-Suk Na, Chan-Su Shin, Alexander Wolff: Constructing Optimal Highways. Int. J. Found. Comput. Sci. 20(1): 3-23 (2009).

2008

[81] Tetsuo Asano, ``Online Uniformity of Integer Points on a Line,'' Inf. Process. Lett. 109(1): 57-60 (2008)

[80] T. Asano, S. Bitou, M. Motoki and N. Usui, “Space-Efficient Algorithm for Image Rotation,” IEICE Transactions 91-A(9): 2341-2348 (2008).

[79] T. Asano, N. Katoh, H. Tamaki, and T. Tokuyama, “Voronoi Diagrams with Respect to Criteria on Vision Information”, Japan Journal of Industrial and Applied Mathematics, Vol.25, pp.1-16, 2008.

[78] Boris Aronov, Tetsuo Asano, Yosuke Kikuchi, Subhas C. Nandy, Shinji Sasahara, and Takeaki Uno: "A Generalization of Magic Squares with Applications to Digital Halftoning," Theory of Computing System, Volume 42, Number 2, pp.143-156, February 2008.

2007

[77] Xuefeng Liang, Arijit Bishnu and Tetsuo Asano, “A Robust Fingerprint Indexing Scheme Using Minutia Neighborhood Structure and Low-order Delaunay Triangles,” IEEE Transactions on Information Forensics and Security，Volume 2, No. 4, pp.721-733, December 2007.

[76] T. Asano, “Aspect-Ratio Voronoi Diagram and Its Complexity Bounds”, Information Processing Letters, volume 105, Issue 1, 31, pp 26-31, December 2007.

[75] T. Asano, J. Matousek, and T. Tokuyama, “Zone diagrams: Existence, Uniqueness and Algorithmic Challenge,” SIAM J. on Computing, Vol.37, Issue 4, pp.1182-1198, September 2007.

[74] X. Liang, A. Bishnu and T. Asano,　"Combinatorial Approach to Fingerprint Binarization and Minutiae Extraction Using Euclidean Distance Transform," International Journal of Pattern Recognition and Artificial Intelligence, vol. 27, no. 7, pp.1141 – 1158, Nov., 2007.

[73] T. Asano, J. Matousek, and T. Tokuyama “The distance trisector curve,” Advances in Mathematics, Vol.212, Issue 1, pp.338-360, 2007.

2006
[72] S. Teramoto T. Asano, N. Katoh, and B. Doerr, “Inserting Points Uniformly at Every Instance,” IEICE Trans. on Info. and Systems, E89-D, 8, pp.2348-2356, 2006

[71] X. Liang and T. Asano, “A Linear Time Algorithm for Binary Fingerprint Image Denoising Using Distance Transform,” IEICE Trans. on e89-D, 4, pp.1534-1542, 2006.

[70] B. Aronov, T.  Asano, N. Katoh, 　K. Mehlhorn, and T. Tokuyama: “Polyline fitting of planar points under min-sum criterion,” International Journal on Computational Geometry and Applications, 16(2-3), pp.97-116, 2006.

[69] T. Asano, P. Evans, R. Uehara, G. Valiente: “Site consistency in phylogenetic networks with recombination,” In Iliopoulos, C.S., Park, K., Steinh¨ofel, K., eds.: Algorithmics in Bioinformatics. Volume 6 of Texts in Algorithmics. College Publications (2006) ch. 2, pp.15-26.

2005

 [68] S. Sasahara and T. Asano: "New Dispersed-dot halftoning technique by elimination of unstable pixels for electrophotography," Journal of Electronic Imaging, pp.023006-1-9, 2005.

[67]T. Asano, M. de Berg, O. Cheong, H. Everett, H. Haverkort, N. Katoh, and A. Wolff: "Optimal Spanners for Axis-Aligned Buildings," Computational Geometry: Theory and Applications, 30, 1, pp.59-77, January 2005.

2004

[66] T. Asano, N. Katoh, H. Tamaki and T. Tokuyama, "The structure and number of global roundings of a graph.", Theoretical Computer Science, Vol.325, pp.425-437, 2004.

[65] T. Shimamoto and T. Asano: "Arranging Fewest Possible Probes to Detect a Hidden Object with Industrial Application," IEICE Trans. Fundamentals, 87-A (5), pp.1053-1058, May 2004. 

[64]  T. Asano, D.G. Kirkpatrick, and C.K. Yap, ``Pseudo-approximation algorithm with applications to optimal motion planning,'' Discrete and Computational Geometry, 31, 1, pp.139-171, 2004.

2003

[63]S. Sasahara, T. Asano, "Adaptive cluster arrangement for Cluster-dot halftoning", Journal of the Imaging Society of Japan, Vol.42 No.4 pp.333-339, 2003

[62] T. Asano, M. de Berg, O. Cheong, L. J. Guibas, J. Snoeyink, and H. Tamaki, "Spanning Trees Crossing Few Barriers," Discrete and Computational Geometry, 30, 4, pp.591-606, 2003.

[61] T. Asano, N. Katoh, K. Obokata, and T. Tokuyama, "Matrix Rounding under the Lp-Discrepancy Measure and Its Application to Digital Halftoning ", SIAM Journal on Computing, 32(6), pp. 1423-1435, December 2003

[60] T.Asano, Y. Kawamura, R. Klette, and K. Obokata, "Digital Curve Approximation with Length Evaluation," IEICE Trans. on Fundamentals, E86-A, 5, May 2003

[59] T. Asano, N. Katoh, K. Obokata, and T. Tokuyama, "Combinatorial and Geometric Problems Related to Digital Halftoning," Lecture Notes of Computer Science, Theoretical Foundations of Computer Vision "Geometry, Morphology, and Computational Imaging," Springer, LNCS 2616, pp.58-71, 2003

[58] T. Asano, "Digital Halftoning: Algorithm Engineering Challenges,"  IEICE Trans. on Inf. and Syst., E86-D, 2, pp.159-178, 2003.

2002

[57] T. Asano, "Algorithmic Evaluation of Line Detection Problem,"  Interdisciplinary Information Sciences, Vol. 8, No.2, pp. 137-145, December 2002.

[56] T. Asano, A. Hernandez-Barrera, and S.C. Nandy, "Translating a convex polyhedron over monotone polyhedra," CGTA: Comput. Geom. Theory and Appli., 23, pp257-269, 2002.

[55] S. C. Nandy, T. Asano, and T. Harayama, "Shattering a set of objects in 2D," Discrete Applied Math., 122 pp.183-194, 2002.

2001

[54]T. Asano, D.Z. Chen, N. Katoh, and T. Tokuyama, "Efficient Algorithms for Optimization-based Image Segmentation," International Journal of Computational Geometry and Applications,11,2,145-166,2001

[53]T. Asano, K. Obokata, T. Tokuyama,"On detecting digital line components in a binary image

," IEICE Trans. on Fundamentals,E84-A,5,1120-1129,May 2001

[52] S.C. Nandy, T. Harayama, and T. Asano: "Dynamically Maintaining the Widest k-dense Corridor, " Theoretical Computer Science, 255, pp.627-639, 2001.

[51] T. Asano, N. Katoh, and T. Tokuyama: "A Unified Scheme for Detecting Fundamental Curves in Binary Edge Images," Computational Geometry: Theory and Applications, vol.18, pp.73-93, 2001.

[50] T. Asano, N. Katoh, and K. Kawashima: " A New Approximation Algorithm for the Capacitated Vehicle Routing Problem on a Tree, ," Journal of Combinatorial Optimization, vol.5, no.2, pp.213-231, 2001.

2000

[49]T. Asano, T. Matsui, and T. Tokuyama,"Optimal Roundings of Sequences and Matrices," Nordic Journal of Computing,17,3,418-427,March 2000 

[48] T. Asano and Y. Kawamura: "Algorithmic Considerations on the Computational Complexities of Digital Line Extraction Problem,"  Trans. IEICE of Japan, Vol.J83-D-I, No.1,pp.80-89, 2000.

[47] T. Asano: "Effective Use of Geometric Information for Clustering and Related Topics," 
IEICE Trans. on Fundamentals, Vol.E83-D, No.3, pp.418-427, March 2000.

[46] T. Asano and Y. Kawamura: " Algorithmic Considerations on the Computational Complexities of Digital Line Extraction Problem," Trans. of IEICE of Japan, Vol.J83-D-I, No.1, pp.80-89, 2000. (in Japanese) 

1999

[45] T. Asano: "Digital Halftoning Algorithm Based on Random Space-Filling Curve,"  IEICE Trans. on Fundamentals, Vol.E82-A, No.3, pp.553-556, March 1999.

1998

[44] T. Asano, S. Kimura, and S. Shimazu: "Contour Representation of an Image with Applications," 
Trans. of IPS of Japan, 39, 12, pp.3242-3251, 1998. (in Japanese)

[43] T. Asano and T. Tokuyama: "Topological Walk Revisited," IEICE Trans. on Fundamentals, vol. E81-A, 5, pp.751-756, 1998.

1997

[42] T. Roos, T. Asano, D. Ranjan, E. Welzl, and P. Widmayer: "Space Filling Curves and Their Use in the Design of Geometric Data Structures," Theoretical Computer Science, 181, pp.3-15, 1997.

1996

[41] T. Asano, D. Ranjan and T. Roos: "Digital Halftoning Algorithms Based on Optimization Criteria and Their Experimental Evaluation," IEICE Trans. Fundamentals, Vol. E79-A, No. 4, pp.524-532, April 1996.

[40] T. Asano and N. Katoh: "Variants for Hough Transform for Line Detection," Computational Geometry: Theory and Applications, vol. 6, pp.231-252 (1996)

1995

[39] T. Asano, N. Katoh, E. Lodi, and T. Roos: "Optimal Approximation of a Curve by a Polygonal Chain with Vertices on a Grid," FORMA (Society for Science on Forms), 10, pp.133-144, 1995.

1994

[38] T. Asano: "Applications of Algorithmic Techniques in Computational Geometry to Image Processing,"
Gazou Lab., October,  pp. 29-32, 1994. (in Japanese)

[37] T. Asano and T. Tokuyama: "Partial Construction of an Arrangement of Lines and Its Application to Optimal Partitioning of Bichromatic Point Set," Trans. of IEICE of Japan, Vol. E77-A, no. 4, pp.595-600, 1994.

[36] N. Kanamaru, T. Nishizeki, and T. Asano: "Efficient Enumeration of Grid Points in a Convex Polygon and its Applications to Integer Programming," Int. J. on Computational Geometry and Applications, Vol. 4, No. 1, pp.69-86, 1994.

[35] T. Asano, L. J. Guibas and T. Tokuyama: "Walking in an Arrangement Topologically" International Journal on Computational Geometry and Applications, Vol. 4, No. 1, pp. 123-151, 1994.

1993

[34] T. Asano and T. Tokuyama: "Circuit Partitioning Algorithms Based on Geometry Modes," Lecture Notes Series on Computing, Vol. 1: "Algorithmic Aspects of VLSI Layout," editied by M. Sarrafzadeh and D.T. Lee, World Scientific, pp.199-212, 1993.

[33] T. Asano and T. Tokuyama:"Algorithms for Projecting Points to Give the Most Uniform Distribution with Applications to Hashing," Algorithmica, vol.9, pp.572-590, 1993

1990

[32] T. Asano and E. Lodi: "Solving Semi-Dynamic Geometric Problems," Trans. of IEICE, vo.E-73, no.2, pp.265-269, 1990.

1989

[31] H. Umeo and T. Asano: "Systolic Algorithms for Computational Geometry Problems--A Survey," Computing, vol.41, nos.1-2, pp.19-40, 1989

1988

[30] T. Asano and Hiroshi Umeo: "Systolic Algorithms for Computing the Visibility Polygon and Triangulation of polygonal region," Parallel Computing, 6, pp.209-216, 1988.

[29] T. Asano: "Generalized Manhattan Path Algorithm with Applications," IEEE Trans. on CAD/ICAS, vol.7, no.7, pp.797-804, July 1988.

1987

[28] Takao Asano, Tetsuo Asano, and H. Imai: "Shortest Path between Two Simple Polygons," Information Processing Letters, vol. 24, pp.285-288, 1987.

1986

[27] T. Asano: "An Algorithm for Finding Angles of Movable Separability between Two Polygons," Trans. of IEICE of Japan, vol. J69-A, no. 9, pp.1162-1165, 1986. (in Japanese)

[26] T. Asano: "Dividing a Simple Polygon into Two Territories," Trans. of IECE of Japan, vol.E-69, no.4, pp.521-523, 1986.

[25] T. Asano: "Rectilinear Shortest Paths in a rectilinear Simple Polygon," Trans. of IECE of Japan,vol. E69, no.6, pp.750-758, 1986.

[24] T. Asano: "Generating and Counting of Valid Patterns of Routes between Two Points," Graphs and Combinatrics An Asian Journal, vol.2, pp.9-13, 1986.

[23] Takao Asano, Tetsuo Asano, L. Guibas, J. Hershberger, and H. Imai: "Visibility of Disjoint Polygon" Algorithmica, vol.1, no.1, pp.49-63, 1986.

[22] Takao Asano, Tetsuo Asano, H. Imai:"Partitioning a Polygonal Region into Trapezoids," J. ACM, vol.33, no.2, pp.290-312, 1986.

[21] Takao Asano, Tetsuo Asano, and R. Y. Pinter:"Polygon Triangulation: Efficiency and minimality," J. Algorithms, vol.7 , pp. 221-231, 1986.

1985

[20] T. Asano: "An Efficient Algorithm for Finding the Region reachable within k Bends," Trans. of IECE of Japan, vol. E-68, no. 12, pp.831-835, 1985.

[19] T. Asano: "On Minimum Width Packing of Rectilinear Blocks," Trans. of IECE of Japan, vol. E-68, no.10, pp.647-649, 1985.

[18] T. Asano: "An Efficient Algorithm for Computing the k-Reachability region from a Point" Trans. of IECE of Japan, vol. E-68, no. 9, pp.560-562, 1985.

[17] T. Asano:"An Efficient Algorithm for Finding the Visibility polygon for a Polygonal Region with Holes," Trans. of IECE of Japan, vol. E-68, no. 9, pp.557-559, 1985.

[16] W.M. Dai, T. Asano, and E.S. Kuh: "Routing Region Definition and Ordering Scheme for Building Block Layout," IEEE Trans. on CAD/ICAS, vol. CAD-4, no.3, pp.189-197, 1985.

1984

[15] Tetsuo Asano, Takao Asano, and Y. Ohsuga:"Partitioning a Polygonal Region into a Minimum Number of Triangles," Trans. of IECE of Japan, vol.E-67, no.4, pp.232-233, 1984.

1982

[14] T. Asano: "Generating All Possible Patterns of Routing Patterns between Two Points," Trans. of IPS of Japan, vol.23, no.5, pp.576-578, 1982. (in Japanese)

[13] T. Asano: "Parallel Global Router," Trans. of IPS of Japan, vol.23, no.4, pp.443-450, 1982. (in Japanese)

[12] T. Asano: "An Optimum Gate Placement Algorithm for MOS One-Dimensional Arrays, " J. of Digital Systems, vol.6, no.1, pp.1-27, 1982.

1981

[11] T. Asano: "On Trunk Division Method for Channel Routing,"Trans. of IEICE of Japan, vol.J64-A, no.7, pp.535-542, 1981. (in Japanese)

[10] T. Asano and N. Yokoya: "Image Segmentation Schema for Low-Level Computer Vision," Pattern Recognition, vol.14, nos., 1-6, pp.267-273, 1981.

1978

[9] N. Yokoya, T. Asano, T. Ohkubo, and K. Tanaka: "Segmentation of an Object from an intensity Image," Trans. of IPS of Japan,  vol.19, no.8, pp.730-737, 1978. (in Japanese)

[8] T. Asano, and K. Tanaka: "A Gate Placement Algorithm for One-Dimensional Arrays," J. of Information Processing, vol.1, no.1, pp.47-52, 1978.

1977

[7] N. Yokoya, T. Asano, T. Ohkubo, and K. Tanaka: "Region Segmentation of an Image Based on a Notion  of Relative Similarity,"  Joho Shori, vol.18, no.12, pp.1223-1231, 1977.(in Japanese)

[6] T. Asano, T. Kitahashi, T. Tanaka, H. Horino, and N. Amano:"A Wire Routing Scheme Based on Trunk Division Methods,"  IEEE Trans. on COMPUTERS, vol.C-26, no.8, pp.764-772, 1977.

1976

[5] T. Asano, T. Kitahashi, and K. Tanaka: "On Realizing Minimum-Width Routing," Trans. of IEICE of Japan, vol.59-A, no.2, pp.115-124, 1976. (in Japanese)

1974

[4] T. Asano, T. Kitahashi, and K. Tanaka: "An Algorithm for Finding a Minimum-Feedback Vertex Set," Trans. of IEICE of Japan, vol.57-A, no.2, pp.153-154, 1974. (in Japanese)

1973

[3] T. Asano, T. Kitahashi, K. Tanaka, H. Horino, and T. Amano: "A Graph-theoretical Consideration on Wire Routing Patterns," Trans. of IEICE of Japan, vol.56-A, no.12, pp.731-738, 1973. (in Japanese)

[2] T. Asano, T. Kitahashi, K. Tanaka, H. Horino, and T. Amano: "On Realizability of Wiring for Building-Block Type LSIs," Trans. of IEICE of Japan, vol.56-A, no.9, pp.489-497, 1973. (in Japanese)

1972

[1] T. Asano, Y. Fujita, T. Kitahashi, and K. Tanaka: "Transformation Matrices between Two Representations of Three-valued Logic Functions," Trans. of IEICE of Japan, vol.55-D, no.6, pp.399-400, 1972. (in Japanese)