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.

[101] Matsuo Konagaya and Tetsuo Asano, "Algorithm for Reporting All Segment Intersections Using  Work Space of Arbitrary Size," to appear in IEICE Trans. EA, Special Section on Discrete Mathematics and Its Applications.

[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.


[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.


[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.


[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,ff Theory of Computing System, vol. 46, No.2, pp.157-173, February 2010.


[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: gFinding Nearest Larger Neighbors: A Case Stgudy in Algorithm Design and Analysis,h Lecture Notes in Computer Science, gEfficient Algorithms,h 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: gSome Generalizations of Least-Squares Algorithms,h  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 ComputingC'' 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,ffComputational Geometry: Theory and Applications, 42(4), pp.289-304,, 2009.

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).


[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, gSpace-Efficient Algorithm for Image Rotation,h IEICE Transactions 91-A(9): 2341-2348 (2008).

[79] T. Asano, N. Katoh, H. Tamaki, and T. Tokuyama, gVoronoi Diagrams with Respect to Criteria on Vision Informationh, 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.


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


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


[75] T. Asano, J. Matousek, and T. Tokuyama, gZone diagrams: Existence, Uniqueness and Algorithmic Challenge,h 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 gThe distance trisector curve,h Advances in Mathematics, Vol.212, Issue 1, pp.338-360, 2007.

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

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

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

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


 [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.


[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.


[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

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


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

6] 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.


[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.


[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) 


[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.


[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.


[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.


[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)


[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.


[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.


[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


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


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


[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.


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


[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.


[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.


[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.


[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.


[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.


[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.


[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.


[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)


[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)


[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)


[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)