Naoki Katoh

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 criteria with respect to L-1- and L-2-metrics, which are more appropriate measures than uniform and Hausdorff metrics in statistical context. We present efficient algorithms for the 1-joint versions of the problem and fully polynomial-time approximation schemes for the general k-joint versions.

This paper presents a floor layout algorithm for a two-story house based on enumeration algorithm as well as optimization algorithm. The process is as follows. First, all floor plans are created based on the floor enumeration algorithm and some of them which have higher values with respect to adjacent relationship and direction requirement are selected. Then, area and shape of those floor layouts are optimized by the tabu search. The proposed method has several advantages over existing methods; (1) Adjacency relationship among rooms is not fixed but the designer is allowed to explore all candidates based on enumeration algorithm of floor plans. (2) The enumeration algorithm employed here has found the all possible combination of 13 rooms. This number is enough to consider general floor layout of a house. (3) This method is applicable to a two-story house. A constraint of the two-story house is effectively used for searching solution in a short time.

A classifier for recognizing glass opening from architectural photographs based on extended Naive Bayes is proposed. From preliminary experiment we determine 3 possible candidates of attributes to represent color pixel each of which uses 6 color characteristics obtained together with x-y coordinates representing the relative position of the pixel in such a way that six color attributes are grouped into three pairs to be used in the extended Naive Bayes. Constructing the classifier based on the extended Naive Bayes which predicts whether a pixel represents glass or not, region segmentation is carried out based on MST. The computer experiments are carried out to demonstrate the effectiveness of the proposed method.

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 structure, which is contrary to the conventional unstable mechanism. Although a compliant mechanism is usually modeled as a continuum with elastic joints, it is possible to generate the similar mechanism by a bar-joint system. Ohsaki and Nishiwaki (Struct. Multidisc. Optim., Vol. 30, pp. 327-334, 2005) presented a method for generating flexible multistable bar-joint mechanisms using nonlinear programming approach. However, due to high nonlinearity of the problem, the nonlinear programming problem should be solved many times starting from different initial solutions to obtain several types of mechanisms. Since the compliant bar-joint mechanism is usually statically determinate, the optimization problem can be solved easily if the design space is limited to statically determinate structures. In this paper, we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-joint frameworks, which are regarded as statically determinate trusses in structural engineering. Bistable mechanisms utilizing snapthrough behavior are generated from the statically determinate trusses. In the numerical examples, many bistable compliant mechanisms are generated to show the effectiveness of the proposed method.

In this paper, we consider the quickest flow problem in a network which consists of a directed graph with capacities and transit times on its arcs. We present an O(n log n) time algorithm for the quickest flow problem in a network of grid structure with uniform arc capacity which has a single sink where n is the number of vertices in the network.

Given a set of line segments in the plane, we define an angular Voronoi diagram as follows: a point belongs to a Voronoi region of a line segment if the visual angle of the line segment from the point is smallest among all line segments. The Voronoi diagram is interesting in itself and different from an ordinary Voronoi diagram for a point set. After introducing interesting properties, we present an efficient algorithms for finding a point to maximize the smallest visual angle. Some applications to mesh improvement are also mentioned. © 2006 IEEE.

We consider the problem of triangulating an x-monotone polygon with a small number of different edge lengths using Steiner points. Given a parameter α, where 0 &lt α &lt 1, we shall present an algorithm for finding an almost uniform triangular mesh with 3π8α2 + o(1α2) different edge lengths such that every edge length is between l and (2 + √2α)l. Experiments demonstrate the effectiveness of this algorithm. Copyright © 2006 The Institute of Electronics, Information and Communication Engineers.

In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks (simply called non-crossing; Laman frameworks) on a given generic set of n points. Our algorithm is based on the reverse search paradigm of Avis and Fukuda. It generates each output graph in O(n(4)) time and O(n) space, or, with a slightly different implementation, in O(n(3)) time and O(n(2)) space. In particular, we obtain that the set of all non-crossing Laman frameworks on a given point set is connected by flips which remove an edge and then restore the Laman property with the addition of a non-crossing edge.

For a given x-monotone polygonal curve each of whose edge lengths is between (l) under bar and 2 (l) under bar, we consider the problem of approximating it by another x-monotone polygonal curve using points of a square grid so that there exists a small number of different edge lengths and every edge length is between (l) under bar and beta(l) under bar, where beta is a given parameter satisfying 1 <= beta <= 2. Our first algorithm computes an approximate polygonal curve using fixed square grid points in O((n/alpha(4)) log(n/alpha)) time. Based on this, our second algorithm finds an approximate polygonal curve as well as an optimal grid placement simultaneously in O((n(3)/alpha(12)) log(2)(n/alpha)) time, where a is a parameter that controls the closeness of approximation. Based on the approximate polygonal curve, we shall give an algorithm for finding a uniform triangular mesh for an x-monotone polygon with a constant number of different edge lengths.

In this study, we propose a method for constructing an estimation model at the early stage of the building project which attains high accuracy and is robust. In the proposed method, the prediction accuracy is improved over the conventional method by focusing on the outliers and modifying the outliers's data when building the prediction model. More concretely, applying the so-called Winsorization mean and the trimmed mean which are known as statistical methods, the proposed methods appropriately modify the amount which is regarded as an outlier in constructing our prediction model. The method is then applied to two types of mutiple regression (L_2 regression and L_1 regression) and two types of neural network (multiple layer network and radial basis function network). In order to quantitatively evaluate the methods, they are applied to real building construction data. It is observed through the experiments that (i) the data modification is in general effective for improving the overall prediction accuracy, (ii) the Winsorization method is superior to the other data modification methods for any of four prediction models, and (iii) both of L_1 regression and the radial basis function network are superior to the other two.

A truss topology optimization problem under stress constraints is formulated as a Mixed Integer Programming (MIP) problem with variables indicating the existence of nodes and members. The local constraints on nodal stability and intersection of members are considered, and a moderately large lower bound is given for the cross-sectional area of an existing member. A lower-bound objective value is found by neglecting the compatibility conditions, where linear programming problems are successively solved based on a branch-and-bound method. An upper-bound solution is obtained as a solution of a Nonlinear Programming (NLP) problem for the topology satisfying the local constraints. It is shown in the examples that upper- and lower-bound solutions with a small gap in the objective value can be found by the branch-and-bound method, and the computational cost can be reduced by using the local constraints.

This paper proposes two methods for identifying images which contain a particular architectural component from a database of architectural images. Applying the techniques of pattern recognition and image retrieval, the first method does this task by using the overall color distribution and the layout. Measuring the similarity between a target image and those whose classes are already known, the method determines the class which a target image belongs to, and it can be applied to classification for many types of architectural components. The second initially selects characteristic elements which will be supposed to play an important role in identifying a particular component, and constructs a model for recognizing such an architectural component by using those characteristic elements. Thus, this method requires us to construct a recognition model from scratch separately for each distinct architectural component, but it attains a higher recognition ability than the first one. The paper then carried out computational experiments by applying the methods to the identification of "tatami" and "lattice" (koshi in Japanese). It was observed that the proposed methods attains a certain level of accuracy and thus are useful for identifying architectural components.

This paper presents an improved algorithm for solving the sum of linear fractional functions (SOLF) problem in 1-D and 2-D. A key subproblem to our solution is the off-line ratio query (OLRQ) problem, which asks to find the optimal values of a sequence of m linear fractional functions (called ratios), each ratio subject to a feasible domain defined by O(n) linear constraints. Based on some geometric properties and the parametric linear programming technique, we develop an algorithm that solves the OLRQ problem in O((m+n)log (m+n)) time. The OLRQ algorithm can be used to speed up every iteration of a known iterative SOLF algorithm, from O(m(m+n)) time to O((m+n)log (m+n)), in 1-D and 2-D. Implementation results of our improved 1-D and 2-D SOLF algorithm have shown that in most cases it outperforms the commonly-used approaches for the SOLF problem. We also apply our techniques to some problems in computational geometry and other areas, improving the previous results.

With the rapid spread of the Internet and the computerization of trading a huge amount of data on the Internet and of transaction database in enterprises has been accumulated. The purpose of this paper is to explain the significance of the technology to process of exabyte-scale data and presents the business application, CODIRO, which will make it possible to integrate various types of large scale data. CODIRO is a consumer research system which discovers new knowledge by integrating the huge amount of different types of data both on the Internet and within companies. This paper will demonstrate the business implications for exabyte-scale information technology research, by explaining an example of the analysis of the sales effectiveness of television commercials using CODIRO.

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 required for data mining. Data format which MUSASHI can deal with is either an XML table written in XML or plain text file with table structure. In this paper we shall present a business application system of MUSASHI, called C-MUSASHI, dedicated to CRM oriented systems. Integrating a large amount of customer purchase histories in XML databases with the marketing tools and data mining technology based on MUSASHI, C-MUSASHI offers various basic tools for customer analysis and store management based on which data mining oriented CRM systems can be developed at extremely low cost. We apply C-MUSASHI to supermarkets and drugstores in Japan to discover useful knowledge for their marketing strategy and present possibility to construct useful CRM systems at extremely low cost by introducing MUSASHI.

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 distance. We consider a generalized version of this notion, where the nodes of the graph are not points but axis-parallel rectangles in the plane. The arcs in the graph are horizontal or vertical segments connecting a pair of rectangles, and the distance measure we use is the L-1-distance. The dilation of a pair of points is then defined as the length of the shortest rectilinear path between them that stays within the union of the rectangles and the connecting segments, divided by their L-1-distance. The dilation of the graph is the maximum dilation over all pairs of points in the union of the rectangles. We study the following problem: given n non-intersecting rectangles and a graph describing which pairs of rectangles are to be connected, we wish to place the connecting segments such that the dilation is minimized. We obtain four results on this problem: (i) for arbitrary graphs, the problem is NP-hard; (ii) for trees, we can solve the problem by linear programming on O(n(2)) variables and constraints; (iii) for paths, we can solve the problem in time O(n(3) logn); (iv) for rectangles sorted vertically along a path, the problem can be solved in O(n(2)) time, and a (1 + epsilon)-approximation can be computed in linear time. (C) 2004 Elsevier B.V. All rights reserved.

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 distance. We consider a generalized version of this notion, where the nodes of the graph are not points but axis-parallel rectangles in the plane. The arcs in the graph are horizontal or vertical segments connecting a pair of rectangles, and the distance measure we use is the L-1-distance. The dilation of a pair of points is then defined as the length of the shortest rectilinear path between them that stays within the union of the rectangles and the connecting segments, divided by their L-1-distance. The dilation of the graph is the maximum dilation over all pairs of points in the union of the rectangles. We study the following problem: given n non-intersecting rectangles and a graph describing which pairs of rectangles are to be connected, we wish to place the connecting segments such that the dilation is minimized. We obtain four results on this problem: (i) for arbitrary graphs, the problem is NP-hard; (ii) for trees, we can solve the problem by linear programming on O(n(2)) variables and constraints; (iii) for paths, we can solve the problem in time O(n(3) logn); (iv) for rectangles sorted vertically along a path, the problem can be solved in O(n(2)) time, and a (1 + epsilon)-approximation can be computed in linear time. (C) 2004 Elsevier B.V. All rights reserved.

Aiming at possible application to detection of several kinds of architectural objects such as windows from two-dimensional digital images, this paper proposes an efficient algorithm for detecting rectangular components in a binary edge image by limiting target objects to those having so-called slicing structure. The proposed algorithm first identifies the regions where ractangular objects may exist by projecting the image intensity data to two axes. It then further narrows the set of candidate edges that are supposed to form a part of rectangles by applying an efficient dynamic programming algorithm. It has been demonstrated through computational experiments that our algorithm attains much higher efficiency and detection accuracy compared with an existing method.

Given a connected weighted graph G = (V, E), we consider a hypergraph H(G) = (V, P(G)) corresponding to the set of all shortest paths in G. For a given real assignment a on V satisfying 0less than or equal toa(v)less than or equal to1, a global rounding a with respect to H(G) is a binary assignment satisfying that \Sigma(vepsilonF)a(v)-alpha(v)\<1 for every F is an element of P(G). We conjecture that there are at most \V\ + 1 global roundings for H(G), and also the set of global roundings is an affine independent set. We give several positive evidences for the conjecture. (C) 2004 Elsevier B.V. All rights reserved.

Given a hypergraph H = (V, F) and a [0, 1]-valued vector a is an element of [0, 1](V), its global rounding is a binary (i.e., {0, 1}-valued) vector a is an element of {0, 1}(V) such that |Sigma(vis an element ofF)(a(v) - alpha(v))| < 1 holds for each F is an element of F. We study geometric (or combinatorial) structure of the set of global roundings of a using the notion of compatible set with respect to the discrepancy distance. We conjecture that the set of global roundings forms a simplex if the hypergraph satisfies "shortest-path" axioms, and prove it for some special cases including some geometric range spaces and the shortest path hypergraph of a series-parallel graph.

We consider the problem of approximating a function on a d-dimensional voxel grid by a unimodal function to minimize the L-2 approximation error with respect to a given measure distribution on the grid. The output unimodal function gives a layered structure on the voxel grid, and we give efficient algorithms for computing the optimal approximation under a reasonable assumption on the shape of each horizontal layer. Our main technique is a dominating cut algorithm for a graph.

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 criteria with respect to L-1- and L-2-metrics, which are more appropriate measures than uniform and Hausdorff metrics in statistical context. We present efficient algorithms for the l-joint versions of the problem, and fully polynomial-time approximation schemes for the general k-joint versions.

The paper concerns a multiobjective heuristic to compute approximate efficient solutions for the assignment problem with two objectives. The aim here is to show that the genetic information extracted from supported solutions constitutes a useful genetic heritage to be used by crossover operators to approximate non-supported solutions. Bound sets describe one acceptable limit for applying a local search over an offspring. Results of extensive numerical experiments are reported. All exact efficient solutions are obtained using Cplex in a basic enumerative procedure. A comparison with published results shows the efficiency of this approach.

This paper presents an optimization method for finding an optimal floor layout of rooms, passages and doorways in a possibly non-rectangular site, based on mathematical programming as well as genetic algorithm. The proposed method has several advantages over existing methods; (1) Adjacency relationship among rooms is not fixed but the designer is allowed to explore a number of candidates based on a sequence-pair and a genetic algorithm. (2) The shape of the building can be changed by introducing virtual rooms. (3) Optimization problem of the passage and doorway layouts is formulated as integer and linear program, respectively. We have implemented the algorithm and tested it for some example.

When one experinces an architectural space, he/she perceives various impressions. The purpose of this paper is to quantitatively clarify the relationship between the impression perceived on a photo of an architectural internal space and the phsical features of its color image. For fifty sample color images of internal space, we have performed a questionaire concerning what impression he/she acquires for each image by asking him/her to choose one of the impression words from a pair of antonyms. Also, we have computed color and texture features of photos. Here we used two-dimensional wavelet transform to obtain texture features while Lab-color space is used to extract color features. We then applied a decision-tree algorithm in order to derive interpretable and meaningful correlation of the impression words and image features. As a result, for images for which a majority of people had the same impression, we have found an interesting, interpretable common feature among the images.

We have recently developed an E-BONSAI (Extended BONSAI) for discovering useful knowledge from time-series purchase transaction data, developed by improving and adding new features to a machine learning algorithm for analyzing string pattern such amino acid sequence, BONSAI, proposed by Shimozono et al. in 1994. E-BONSAI we developed can create a good decision tree to classify positive and negative data for records whose attributes are either numerical, categorical or string patterns while other methods such as C5.0 and CART cannot deal with string patterns directly. We shall demonstrate advantages of E-BONSAI over existing methods for forecasting future demands by applying the methods to real business data. To demonstrate an advantage of E-BONSAI for business application, it is significant to evaluate it from the two perspectives. The first is the objective and technical perspective such as the prediction accuracy. The second is the management perspective such as the interpreterability to create new business action. Applying the E-BONSAI to forecast how long new products survive in instant noodle market in Japan, we have succeeded in attaining high prediction ability and discovering useful knowledge for domain experts.

We study the problem of rounding a real-valued matrix into an integer-valued matrix to minimize an L-p-discrepancy measure between them. To de. ne the L-p-discrepancy measure, we introduce a family F of regions ( rigid submatrices) of the matrix and consider a hypergraph defined by the family. The difficulty of the problem depends on the choice of the region family F. We first investigate the rounding problem by using integer programming problems with convex piecewise-linear objective functions and give some nontrivial upper bounds for the L-p discrepancy. We propose "laminar family" for constructing a practical and well-solvable class of F. Indeed, we show that the problem is solvable in polynomial time if F is the union of two laminar families. Finally, we show that the matrix rounding using L-1 discrepancy for the union of two laminar families is suitable for developing a high-quality digital-halftoning software.

We consider the problem of triangulating a convex polygon using n Steiner points under the following optimality criteria: (1) minimizing the overall edge length ratio; (2) minimizing the maximum edge length; and (3) minimizing the maximum triangle perimeter. We establish a relation of these problems to a certain extreme packing problem. Based on this relationship, we develop a heuristic producing constant approximations for all the optimality criteria above (provided n is chosen sufficiently large). That is, the produced triangular mesh is uniform in these respects. The method is easy to implement and runs in O(n(2) logn) time and O(n) space. The observed runtime is much less. Moreover, for criterion (1) the method works-within the same complexity and approximation bounds-for arbitrary polygons with possible holes, and for criteria (2) and (3) it does so for a large subclass. (C) 2002 Elsevier Science B.V. All rights reserved.

We give an optimal bound on the number of transitions of the minimum weight base of an integer valued parametric polymatroid. This generalizes and unifies Tamal Dey's O(k(1/3)n) upper bound on the number of k-sets (and the complexity of the k-level of a straight-line arrangement), David Eppstein's lower bound on the number of transitions of the minimum weight base of a parametric matroid, and also the Theta(kn) bound on the complexity of the at-most-k level (the union of i-levels for i = 1, 2,..., k) of a straight-line arrangement. As applications, we improve Welzl's upper bound on the sum of the complexities of multiple levels, and apply this bound to the number of different equal-sized-bucketings of a planar point set with parallel partition lines. We also consider an application to a special parametric transportation problem.

Symmetricity of an optimal solution of Semi-Definite Programming (SDP) is discussed based on the symmetry property of the central path that is traced by a primal-dual interior-point method. A symmetric SDP is defined by operators for rearranging elements of matrices and vectors, and the solution on the central path is proved to be symmetric. Therefore, it is theoretically guaranteed that a symmetric optimal solution is always obtained by using a primal-dual interior-point method even if there exist other asymmetric optimal solutions. The optimization problem of symmetric trusses under eigenvalue constraints is shown to be formulated as a symmetric SDP. Numerical experiments illustrate convergence to strictly symmetric optimal solutions.

A method is presented for finding optimal prestresses of cable-supported frames as well as order of tensioning cables and removing temporary supports, which is refered to as construction order. The cable forces at the final state are first optimized, and the construction process is inversely traced. In the prestress optimization, prestresses of cables are modeled as external forces. Constraints are given for stresses and displacements of the frame. Two methods are presented for optimization of construction order of cable-supported frames considering constraints on stresses of the frame and cables. The globally optimal order is found by the dynamic programming approach. An approximate method is also presented based on a heuristic measure for selecting a cable or a temporary support at each step while tracing the inverse construction process only once.

We show that for any line l in space, there are at most k(k + 1) tangent planes through l to the k-level of an arrangement of concave surfaces, This is a generalization of Lovasz's lemma. which is a key constituent in the analysis of the complexity of k-levels of planes. Our proof is constructive, and finds a family of concave surfaces covering the "laminated at-most-k-level." As a consequence, (1) we have an O((n-k)(2/3) n(2))upperbound for the complexity of the k-level of n triangles of space, and (2) we can extend the k-set result in space to the k-set of a system of subsets of n points.

In this paper we study the problem of rounding a real-valued matrix into an integervalued matrix to minimize an L_p-discrepancy measure between them. To define the L_p-discrepancy measure, we introduce a family F of regions (rigid submatrices) of the matrix, and consider a hypergraph defined by the family. This paper shows how the difficulty of the problem depends on the choice of the region family F.

A class of group symmetric Semi-Definite Program (SDP) is introduced by using the framework of group representation theory. It is proved that the central path and several search directions of primal-dual interior-point methods are group symmetric. Preservation of group symmetry along the search direction theoretically guarantees that the numerically obtained optimal solution is group symmetric. As an illustrative example, we show that the optimization problem of a symmetric truss under frequency constraints can be formulated as a group symmetric SDP. Numerical experiments using an interior-point algorithm demonstrate convergence to strictly group symmetric solutions.

This paper presents a new approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. Customers are located on vertices of the tree, and each customer has a positive demand. Demands of customers are served by a fleet of identical vehicles with limited capacity. It is assumed that the demand of a customer is splittable, i.e., it can be served by more than one vehicle. The problem we are concerned with in this paper asks to find a set of tours of the vehicles with minimum total lengths. Each tour begins at the depot, visits a subset of the customers and returns to the depot without violating the capacity constraint. We propose a 1.35078-approximation algorithm for the problem (exactly, (root 41 - 1)/4), which is an improvement over the existing 1.5-approximation.