Fast enumeration algorithms for non-crossing geometric graphs (2009)
Katoh, Naoki, Tanigawa, Shin-Ichi
A non-crossing geometric graph is a graph embedded on a set of points in the plane with non-crossing straight line segments. In this paper we present a general framework for enumerating non-crossing...
A Proof of the Molecular Conjecture (2009)
Katoh, Naoki, Tanigawa, Shin-ichi
A $d$-dimensional body-and-hinge framework is, roughly speaking, a structure consisting of rigid bodies connected by hinges in $d$-dimensional space. The generic infinitesimal rigidity of a...
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....
Enumerating Constrained Non-crossing Minimally Rigid Frameworks (2008)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints, which we call constrained...
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...
Theoretical and Practical Issues of Evacuation Planning in Urban Areas (2008)
Naoyuki Kamiyama, Naoki Katoh, Atsushi Takizawa
In December 2004, the Sumatra-Andaman earthquake occurred. It triggered tsunamis, and tragedy fell upon many people. Not only earthquakes but also diverse disasters occurred and caused serious...
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...
Covering Directed Graphs by In-trees (2008)
Kamiyama, Naoyuki, Katoh, Naoki
Given a directed graph $D=(V,A)$ with a set of $d$ specified vertices $S=\{s_1,...,s_d\}\subseteq V$ and a function $f\colon S \to \mathbb{Z}_+$ where $\mathbb{Z}_+$ denotes the set of non-negative...
Enumeration of Optimal Pin-Jointed Bistable Compliant Mechanisms (2008)
Naoki Katoh, Makoto Ohsaki, Takuya Kinoshita, Shin-ichi Tanigawa, David Avis, Ileana Streinu
Recently, a new type of mechanism called compliant mechanism has been developed and applied mainly in the field of micro-mechanics. A compliant mechanism has flexible parts to stabilize the...
Data Mining Oriented CRM Systems Based on MUSASHI: C-MUSASHI ⋆ (2008)
Katsutoshi Yada, Yukinobu Hamuro, Naoki Katoh, Takashi Washio, Issey Fusamoto, Daisuke Fujishima, ...
Abstract. MUSASHI is a set of commands which enables us to efficiently execute various types of data manipulations in a flexible manner, mainly aiming at data processing of huge amount of data...
Enumerating constrained non-crossing minimally rigid frameworks (2008)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
Voronoi diagrams with respect to criteria on vision information (2008)
Asano, Tetsuo, Katoh, Naoki, Tamaki, Hisao, Tokuyama, Takeshi
Arc-disjoint in-trees in directed graphs (2008)
Kamiyama, Naoyuki, Katoh, Naoki, Takizawa, Atsushi
Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Dis crete Algorithms, San Francisco, CA, January 20-22, 2008 ; This symposium was sponsored by the ACM Special Interest Group on Algorithms...
Fast enumeration algorithms for non-crossing geometric graphs (2008)
Katoh, Naoki, Tanigawa, Shin-ichi
Proceedings of the twenty-fourth annual symposium on Computational geometry 2008, College Park, MD, USA, June 09-11, 2008
Covering Directed Graphs by In-Trees (Computing and Combinatorics) (2008)
Kamiyama, Naoyuki, Katoh, Naoki
Computing and Combinatorics : 14th annual international conference, COCOON 2008, Dalian, China, June 27-29, 2008 : (Lecture notes in computer science ; 5092)
Geometric Spanner of Objects under L1 Distance (Computing and Combinatorics) (2008)
Zhu, Yongding, Xu, Jinhui, Yang, Yang, Katoh, Naoki, Tanigawa, Shin-ichi
Computing and combinatorics : 14th annual international conference, COCOON 2008, Dalian, China, June 27-29, 2008 : proceedings : (Lecture notes in computer science ; 5092)
Kamiyama, Naoyuki, Katoh, Naoki, Takizawa, Atsushi
Algorithmic aspects in information and management : Third International Conference, AAIM 2007, Portland, OR, USA, June 6-8, 2007 : proceedings : (Lecture notes in computer science ; 4508)
Kontrolle Projektbereich Diskrete, Diskrete Optimierung, Gunter Rote, Triangulations Intersect Nicely, Oswin Aichholzer, Oswin Aichholzer, ...
We show that there is a matching between the edges of any two triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other...
Katsuki Fujisawa, Yukinobu Hamuro, Naoki Katoh, Takeshi Tokuyama, Katsutoshi Yada
. We consider the problem of finding two-dimensional association rules for categorical attributes. Suppose we have two conditional attributes A and B both of whose domains are categorical, and one...
Symmetricity Of The Solution Of Semidefinite Program (2007)
Yoshihiro Kanno, Makoto Ohsaki, Katsuki Fujisawa, Naoki Katoh
. Symmetricity of an optimal solution of SemiDefinite Program (SDP) with certain symmetricity is discussed based on symmetry property of the central path that is traced by a primaldual interior-point...
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...
Discovering Purchase Association among Brands from Purchase History (2007)
Yukinobu Hamuro, Naoki Katoh, Katsutoshi Yada, Taihei Yano
Abstract—Analyzing purchase history of customers enables us to discover valuable knowledge that is helpful for developing effective sales promotion. In this respect, we shall introduce a new...
Danny Z. Chen, Ovidiu Daescu, Yang Dai, Naoki Katoh, Xiaodong Wu, Jinhui Xu
The problem of optimizing the sum of m linear fractional functions (SOLF) in a xed dimension d, subject to n linear constraints, arises in a number of theoretical and applied areas. This paper...
Danny Z. Chen, Ovidiu Daescu, Yang Dai, Naoki Katoh, Xiaodong Wu, Jinhui Xu
The problem of optimizing the sum of m linear fractional functions (SOLF) in a xed dimension d, subject to n linear constraints, arises in a number of theoretical and applied areas. This paper...
A New Probabilistic Analysis of Karger's Randomized Algorithm for Minimum Cut Problems (2007)
Yang Dai, Kazuo Iwano, Naoki Katoh
Recently Karger proposed a new randomized algorithm for finding a minimum cut of an n-vertex graph (weighted or unweighted) with probability\Omega n
Generalized LMT-Skeleton Heuristics for Several New Classes of Optimal Triangulations 1 (2007)
Yang Dai, Naoki Katoh, Siu-wing Cheng
Given a planar point set, we consider three classes of optimal triangulations: (1) the minimum weight triangulation with angular constraints (constraints on the minimum angle and the maximum angle in...
NTT Data Communications Systems Corporation Hiroshi Imai (2007)
Susumu Hasegawa, Mary Inaba, Naoki Katoh
In this paper we consider the k-clustering problem for n points in the d-dimensional space, motivated from the problem of computing a color lookup table for frame buffer display, and that of...
to Journal of Mathematical Modelling and Algorithms (2007)
Xavier G, Naoki Katoh, Xavier Gandibleux, Hiroyuki Morita, Hiroyuki Morita
for solving the assignment problems with two objectives
Yada, Katsutoshi, Ip, Edward, Katoh, Naoki
Decision tree methodology has become an increasingly important tool set in the field of decision science. We develop a multivariate, tree-based decision system for a new application: the...
Takizawa, Atsushi, Yoshida, Kazuma, Katoh, Naoki
2007 IEEE International Conference on Systems, Man and Cybernetics, Mo ntreal, QC, Canada, 7-10 October 2007. : IEEE catalog number: CFP07SMC-PRT
Enumerating non-crossing minimally rigid frameworks (2007)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
Geometric Spanner of Segments (Algorithms and Computation) (2007)
Yang, Yang, Zhu, Yongding, Xu, Jinhui, Katoh, Naoki
Algorithms and computation : 18th International Symposium, ISAAC 2007, Sendai, Japan, December 17-19, 2007 : proceedings ; ISAAC 2007 : (Lecture notes in computer science ; 4835)
Enumerating Constrained Non-crossing Geometric Spanning Trees (Computing and Combinatorics) (2007)
Katoh, Naoki, Tanigawa, Shin-ichi
Computing and combinatorics : 13th Annual International Conference, COCOON 2007 Banff, Canada, July 16-19, 2007 : proceedings : (Lecture notes in computer science ; 4598)
An approximation algorithm for the pickup and delivery vehicle routing problem on trees (2006)
This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot where there are two types of demands, pickup demand and delivery demand....
Enumerating Constrained Non-crossing Minimally Rigid Frameworks (2006)
Avis, David, Katoh, Naoki, Ohsaki, Makoto, Streinu, Ileana, Tanigawa, Shin-ichi
In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints (also called constrained...
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...
Enumerating planar minimally rigid graphs (2006)
David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-ichi Tanigawa
Motivated by the work of Kawamoto et al. [5], who first suggested the use of graph enumeration techniques as an engineering tool for finding an optimum mechanism design, we give an algorithm for...
Enumerating planar minimally rigid graphs (2006)
David Avis, Naoki Katoh, Makoto Ohsaki, Ileana Streinu, Shin-ichi Tanigawa
Abstract. We present an algorithm for enumerating without repetitions all the planar (noncrossing) minimally rigid (Laman) graphs embedded on a given generic set of n points. Our algorithm is based...
Inserting points uniformly at every instance (2006)
Teramoto, Sachio, Asano, Tetsuo, Katoh, Naoki, Doerr, Benjamin
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...
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...
Kamiyama, Naoyuki, Katoh, Naoki, Takizawa, Atsushi
Algorithmic aspects in information and management : Second International Conference, AAIM 2006, Hong Kong, China, June 20-22, 2006 : proceedings : (Lecture notes in computer science ; 4041)
The Future Direction of New Computing Environment for Exabyte Data in the Business World (2005)
Yada, Katsutoshi, Hamuro, Yukinobu, Katoh, Naoki, Kishiya, Kazuhiro
Applications and the Internet Workshops, 2005. Saint Workshops 2005. The 2005 Symposium on 31-04 Jan. 2005
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...
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, ...
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
Polyline Fitting of Planar Points Under Min-sum Criteria (2004)
Aranov, Boris, Asano, Tetsuo, Katoh, Naoki, Mehlhorn, Kurt, Tokuyama, Takeshi, Fleischer, Rudolf, ...
A faster algorithm for two-variable integer programming (2003)
Eisenbrand, Friedrich, Laue, Soeren, Ibaraki, Toshihide, Katoh, Naoki, Ono, Hirotaka
We show that a 2-variable integer program, defined by $m$ constraints involving coefficients with at most $\varphi$ bits can be solved with $O(m + \varphi)$ arithmetic operations on rational numbers...
Approximating uniform triangular meshes in polygons,” Theor (2002)
Franz Aurenhammer, Naoki Katoh, Hiromichi Kojima, Makoto Ohsaki, Yinfeng Xu
Given a convex polygon P in the plane and a positive integer n, weconsider the problem of generating a length-uniform triangular mesh for the interior of P using n Steiner points. More specifically,...
Notes on computing peaks in k-levels and parametric spanning trees (2001)
Katoh, Naoki, Tokuyama, Takeshi
We give an algorithm to compute all the local peaks in the $k$-level of an arrangement of $n$ lines in $O(n \log n) + \tilde{O}((kn)^{2/3})$ time. We can also find $\tau$ largest peaks in $O(n \log...
Asano, Tetsuo, Fujikawa, Naoki, Katoh, Naoki, Matsui, Tomomi, Nagamochi, Hiroshi, Tokuyama, Takeshi, ...
Notes on computing peaks in k-levels and parametric spanning trees (2001)
Katoh, Naoki, Tokuyama, Takeshi
Proceedings of the Seventeenth Annual Symposium on Computational Geometry, (SCG '01), June 3-5, 2001, Medford, Massachusetts, USA / sponsored by the ACM Special Interest Group for Graphics and...
Finding an Optimal Region in One- and Two-Dimensional Arrays (2000)
Given N real weights w?1, w?2, ..., w?N stored in one-dimensional array, we consider the problem for finding an optimal interval I ⊂[1, N]under certain criteria. We shall review efficient...
Optimizing the sum of linear fractional functions and applications (2000)
Chen, Danny Z., Daescu, Ovidiu, Dai, Yang, Katoh, Naoki, Wu, Xiadong, Xu, Jinhui
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, January 9-11, 2000 -- T.p. verso ; This symposium was sponsored by the ACM Special Interest...
Approximating Uniform Triangular Meshes in Polygons (Algorithm Engineering as a New Paradigm) (1999)
Aurenhammer, Franz, Katoh, Naoki, Ohsaki, Makoto, Xu, Yin-Feng
Katsuki Fujisawa, Yukinobu Hamuro, Naoki Katoh, Takeshi Tokuyama, Katsutoshi Yada
Abstract. We consider the problem of finding two-dimensional association rules for categorical attributes. Suppose we have two conditional attributes A and B both of whose domains are categorical,...
Finding Subsets Maximizing Minimum Structures (1999)
Halldórsson, Magnús M., Iwano, Kazuo, Katoh, Naoki, Tokuyama, Takeshi
We consider the problem of finding a set of k vertices in a graph that are in some sense remote. Stated more formally, given a graph G and an integer k, find a set P of k vertices for which the total...
Lovasz's lemma for the three-dimensional k-level of concave surfaces and its applications (1999)
1 Introduction Investigation of the combinatorial properties of k-levels of arrangements of curves and surfaces is a central topic in combinatorial geometry. The k-level problem can be considered as...
Improvement in the High-Temperature Oxidation Resistance of TiAl by Sol-Derived SiO2 Coating. (1998)
Taniguchi, Shigeji, Shibata, Toshio, Katoh, Naoki
TiAl specimens were coated with sol-derived SiO2 coating to study high temperature oxidation resistance. The specimens were subjected to purified oxygen at temperatures of 1100, 1200 and 1300 K. At...
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...
Computing New Classes of Optimal Triangulations with Angular Constraints (1998)
Given a planar point set S, a triangulation of S is a maximal set of nonintersecting edges connecting points in S. Triangulating a point set has many applications in computational geometry and other...
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...
Triangulations Intersect Nicely (1996)
Oswin Aichholzer, Oswin Aichholzer, Franz Aurenhammer, Franz Aurenhammer, Günter Rote, Michael Taschwer, ...
We show that there is a matching between the edges of anytwo triangulations of a planar point set such that an edge of one triangulation is matched either to the identical edge in the other...
Finding Subsets Maximizing Minimum Structures (1995)
Magnús M. Halldórsson, Kazuo Iwano, Naoki Katoh, Takeshi Tokuyama
We consider the problem of finding a set of k vertices in a graph that are in some sense remote, stated more formally: "Given a graph G and an integer k, and a set P of k vertices for which the...
Theoretical Aspects of Object-Oriented Programming - Types, Semantics, and Language Design (1993)
Carl A. Gunter, John C. Mitchell (eds.), John C. Mitchell, Michael Garey, Albert Meyer, Naoki Katoh
ion. John C. Reynolds 13 2 Using Category Theory to Design Implicit Conversions and Generic Operators. John C. Reynolds 14 II Type Inference 15 3 Type Inference for Records in a Natural Extension of...