List of Publications
Tetsuo Asano
Kanazawa University
Ph.D. Thesis (Doctor of Engineering)”Wire Routing Scheme Based on Graph Theory Model” Graduate School of Osaka University,
School of Engineering Science, 1977.
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.
[103] Tetsuo Asano, Lilian Buzer, Sergey Bereg: “ A new algorithmic framework for basic problems
on binary images ,” Discret. Appl. Math. 216: 376-392 (2017)[102] Tetsuo Asano, Kevin Buchin, Maike Buchin, Matias Korman, Wolfgang Mulzer, Gunter Rote,Andre Schulz:“ Memory-constrained algorithms for simple polygons,” Comput. Geom. 46(8): 959-969(2013)[101] Tetsuo Asano, Revant Kumar: “ A Small-Space Algorithm for Removing Small Connected
Components from a Binary Image ,” IEICE Trans. Fundam. Electron. Commun. Comput. Sci.
96-A(6): 1044-1050 (2013)[100] Tetsuo Asano, Jesper Jansson, Kunihiko Sadakane, Ryuhei Uehara, Gabriel Valiente: “ Fastercomputation of the Robinson-Foulds distance between phylogenetic networks ,” Inf. Sci. 197: 77-90(2012)[99] Tetsuo Asano, Erik D. Demaine, Martin L. Demaine, and Ryuhei Uehara: “ NP-completenessof Generalized Kaboozle,” 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,” InformationSciences, 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)1

[94] T. Asano, W. Mulzer, G. Rote, Y. Wang,“Constant-work-space Algorithms for GeometricProblems,” 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,” Journalof 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 withsteiner 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: Aperspective. Discrete Applied Mathematics, 157(16), pp: 3362-3371, 2009.
[87] Tetsuo Asano, Sergey Bereg, and David Kirkpatrick: Finding Nearest Larger Neighbors: ACase 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 Generalizationsof 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 LinearSpace Algorithm for Distance Preserving Graph Embedding,Computational Geometry: Theory andApplications, 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 SecurityVolume 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 andMinutiae 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 withrecombination, In Iliopoulos, C.S., Park, K., Steinhofel, 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 unstablepixels 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 AxisAligned 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 ofthe 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 LpDiscrepancy 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. andSyst., 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 overmonotone 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 Optimizationbased Image Segmentation,” International Journal of Computational Geometry and Applications,11,2,145166,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. (inJapanese)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 OptimizationCriteria 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,” ComputationalGeometry: 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.E73, 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 andTriangulation 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.E69, no.4, pp.521-523, 1986.
[25] T. Asano: ”Rectilinear Shortest Paths in a rectilinear Simple Polygon,” Trans. of IECE ofJapan,vol. E69, no.6, pp.750-758, 1986.
[24] T. Asano: ”Generating and Counting of Valid Patterns of Routes between Two Points,” Graphsand 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. ofInformation 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 ona 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 Basedon 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. ofIEICE 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. (inJapanese)[2] T. Asano, T. Kitahashi, K. Tanaka, H. Horino, and T. Amano: ”On Realizability of Wiring forBuilding-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.399400, 1972. (in Japanese)