加藤 直樹

Street crimes such as auto theft and snatch theft account for approximately half of all crimes committed in Japan. The strategy of CPTED (Crime Prevention through Environmental Design) is now drawing the attention of urban planners and architects. Recently, the effectiveness of CPTED has been empirically examined using GIS. In this article, the authors investigate the relationship between snatch theft and the spatial attributes of the suburbs of Kyoto City. The spatial attributes considered include demographic data, land-use, visibility of space, and illuminance on the street. These attributes are analyzed with a significance test of mean as well as via CAEP (Classification by Aggregating Emerging Patterns). From these analyses, the authors obtain the following conclusions: (i) Mean values of pedestrians, population, and visibility of non-housing sites are relatively high at snatch theft locations. (ii) Illuminance on the street is not a predominant factor. (iii) Primary spatial patterns of snatch theft locations include relatively high visibility of a public facility site. (iv) The classification accuracy of CAEP is higher than that of other general classifiers. (v) In residential areas, the risk of snatch theft tends to be high only at particular sites. Meanwhile, downtown, it can occur frequently regardless of the site.

Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set S of n disjoint 2-D segments, find a spanning network G(S) with minimum size so that for any pair of points in S, there exists a path in G(S) with length no more than t times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, interval cover, and imaginary Steiner points), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set Q of Steiner points in S and then constructs a point spanner for the set of Steiner points. Our algorithm runs in O(vertical bar Q vertical bar+n(2) log n) time and Q is a constant approximation (in terms of its size) of the optimal solution when S has a constant relative separation ratio. The approximation ratio depends on the stretch factor t and the relative separation ratio of S.

Parametric search is a useful tool in geometric optimization. Invented by Nimrod Megiddo in 1983, it has been widely used in computational geometry. Unfortunately, this technique has rarely been used in the combinatorial optimization community in China. In this paper, we introduce parametric search via three new geometric optimization applications.

A rooted-forest is a graph having self-loops such that each connected component contains exactly one loop, which is regarded as a root, and there exists no cycle consisting of non-loop edges. In this paper, we shall study on a. partition of a graph into edge-disjoint rooted-forests such that each vertex is spanned by exactly d components of the partition, where d is a positive integer.

In this paper, we consider the evacuation problem in a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [B. Hoppe, E. Tardos, The quickest transshipment problem, Math. Oper. Res. 25(1) (2000) 36-62] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus, it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a network with a sink s such that (i) for each vertex v not equal s the sum of the transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v not equal s the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. This class of networks is a generalization of grid networks studied in the paper [N. Kamiyama, N. Katoh, A. Takizawa, An efficient algorithm for evacuation problem in dynamic network flows with uniform arc capacity, IEICE Trans. Infrom. Syst. E89-D (8) (2006) 2372-2379]. We propose an efficient algorithm for this network problem. (C) 2009 Elsevier B.V. All rights reserved.

In this paper, we present algorithms for enumerating, without repetitions, all triangulations and non-crossing geometric spanning trees on a given set of n points in the plane under edge inclusion constraint (i.e., some edges are required to be included in the graph). We will first extend the lexicographically ordered triangulations introduced by Bespamyatnikh to the edge-constrained case, and then we prove that a set of all edge-constrained non-crossing spanning trees is connected via remove-add flips, based on the edge-constrained lexicographically largest triangulation. More specifically, we prove that all edge-constrained triangulations can be transformed to the lexicographically largest triangulation among them by O(n(2)) greedy flips, i.e., by greedily increasing the lexicographical ordering of the edge list, and a similar result also holds for a set of edge-constrained non-crossing spanning trees. Our enumeration algorithms generate each output triangulation and non-crossing spanning tree in O(log log n) and O(n(2)) time, respectively, based on the reverse search technique. (C) 2009 Elsevier B.V. All rights reserved.

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 geometric graphs on a given point set. Applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees, and non-crossing minimally rigid graphs. Our idea also produces efficient enumeration algorithms for other graph classes, for which no algorithm has been reported so far, such as non-crossing matchings, non-crossing red-and-blue matchings, non-crossing k-vertex or k-edge connected graphs, or non-crossing directed spanning trees. The proposed idea is relatively simple and potentially applies to various other problems of non-crossing geometric graphs.

根つき森の各根をループ付きの頂点として捉えることで,根つき森は各連結成分に一つのループを有し,かつサイクルが存在しない無向グラフとして定義する事が出来る.本稿では,ループを有するグラフG=(V,E)と正の整数dが与られた際,各頂点がd回張られるような辺素根つき森(および辺素根つき木)への分割可能性について論じる.また森分割と構造物の剛性との関連について解説を行う.

Given a directed graph D = (V, A) with a set of d specified vertices S = {s(1), . . . , s(d)} subset of V and a function f : S -> N where N denotes the set of natural numbers, we present a necessary and sufficient condition such that there exist Sigma(d)(i=1) f(s(i)) arc-disjoint in-trees denoted by T(i,1),T(i,2), . . . ,T(i,f(si)) for every i = 1, . . . ,d such that T(i,1), . . . , T(i,f(si)) are rooted at s(i) and each T(i,j) spans the vertices from which si is reachable. This generalizes the result of Edmonds [2], i.e., the necessary and sufficient condition that for a directed graph D=(V,A) with a specified vertex s is an element of V, there are k arc-disjoint in-trees rooted at s each of which spans V. Furthermore, we extend another characterization of packing in-trees of Edmonds [1] to the one in our case.

An optimization approach is presented for enumerating pin-jointed bistable compliant mechanisms. In the first stage, the statically determinate trusses with non-crossing members containing a given set of nodes and some pre-defined members are regarded as minimally rigid framework or a Laman framework, and are enumerated without repetitions by the graph enumeration algorithm. In the second stage, the nodal locations and the cross-sectional areas are optimized under mechanical constraints, where the snapthrough behavior is extensively utilized to produce a pin-jointed bistable compliant mechanism. In the numerical examples, many bistable compliant mechanisms are generated to show the effectiveness of the proposed method.

特別な点 r ∈ V を持つ有向グラフ D = (V，A) 上で，r を根とする辺素な有向木族やその点素版である独立有向木族を求める問題は，理論的にも応用的にも重要な問題であり広く研究されてきた．近年， Edmonds ［1］ によって示された辺素な有向木族に関する特徴付けが， 神山等 ［5］ の結果を元に藤重 ［2］ によって拡張された．本論文では， Whitty ［6］ や Huck ［4］ によって与えられた独立有向木族に対する結果が，藤重 ［2］ による辺素な有向木族の特徴付けの拡張と同様に拡張できることを示す．The problem of finding arc-disjoint arborescences rooted at r or independent arborescences rooted at r which are a vertex-disjoint analogue of arc-disjoint arborescences in a directed graph D = (V,A) with a specified vertex r ∈ V is very important from not only the theoretical viewpoint but also the practical viewpoint. Recently, Fujishige extended the characterization on arc-disjoint arborescences presented by Edmonds based on the result of Kamiyama et al.. In this paper, we prove that the results presented by Whitty and Huck on independent arborescences can be extended in the same manner as Fujishige's extension of Edmonds' theorem on arc-disjoint arborescences.

Least-squares method is often used for solving optimization problems such as line fitting of a point sequence obtained by experiments. This paper describes some extensions of the method and presents an application to some completely different geometric optimization problem. Given a sorted sequence of points (x(1),y(1)), (x(2),y(2)), ..., (x(n),y(n)), a line y = ax +b that optimally approximates the sequence can be computed by determining the constants a and b that minimizes the sum of squared distances to the line, which is given by Sigma(n)(i=1) (ax(i) + b - y(i))(2). It suffices to solve a system of linear equations derived by differentiating the sum by a and b. In this paper we extend the problem of approximating a point sequence by a 1-joint polyline. Another problem we consider is a geometric optimization problem. Suppose we are given a set of points in the plane. We want to insert a new point so that distances to existing points are as close as those distances specified as input data. If the criterion is to minimize the sum of squared errors, an application of the same idea as above combined with a notion of arrangement of lines leads to an efficient algorithm.

In evacuation situations, it is very important that we have enough refuges. Therefore, we have to check in advance if capacities of refuges in urban areas are sufficiently large. In this paper, we present an algorithm for this problem by using a dynamic network flow which is a branch of the network flow theory, and then we apply our method to a numerical example modeling Kyoto City in Japan.

A body-and-hinge framework is a structure consisting of rigid bodies connected by hinges in d-dimensional space. The generic infinitesimal rigidity of a body-and-hinge framework has been characterized in terms of the underlying graph independently by Tay and Whiteley as follows: A graph G can be realized as an infinitesimally rigid body-and-hinge framework by mapping eaacah ve rtex to a body anda each edge to a hinge if and only if ((d+12)-1) G contains( d+12) edgedisjoint spanning trees, where ((d+12)-1) G is the graph obtained from G by replacing each edge by ((d+12)-1) parallel edgesa. In 1984 they JOintely posed a question about whether their combinatorial characterization can be further applied to a nongeneric case. Specifically, they conjectured that G can be realized as an infinitesimally rigid body-and-hinge framwork if and only if G can be realized as that with the additional "hinge-copanar" property, i.e., all the hinges incident to each body are contained in a common hyperplane. This conjecture is called the Molecular Conjecture due to the equivalence between th infinitesimal rigidity of "hinge-coplanar" body-and -hinge framworks and that of bar-and-joint frameworks derved from molecules in 3-dimension. In 2-dimensional case this conjecture has been proved by jackson and jordáan in 2006. In this paper we prove this long standing conjecture affirmatively ofr general dimension. Also, as a corollary, we obtain a combinatorialcharacterization of the 3-dimensional bar-and-joint rigidity matroid of the square of a graph. © 2009 ACM.

In this paper, we consider the universally quickest transshipment problem in a dynamic network where each arc has not only a capacity but also a transit time. The problem asks for minimizing the time when the last supply reaches the sink as well as simultaneously maximizing the amount of supply which has reached the sink at every time step. In this paper, we propose a polynomial-time algorithm for the problem in the class of dynamic networks which is a generalization of grid networks with uniform capacity and uniform transit time.

A bar-slider framework is a bar-joint framework a part of whose joints are constrained by using line-sliders. Such joints are allowed to move only along the sliders. Streinu and Theran proposed a combinatorial characterization of the infinitesimal rigidity of generic bar-slider frameworks in two dimensional space. In this paper we propose a generalization of their result. In particular, we prove that, even though the directions of the sliders are predetermined and degenerate, i.e., some sliders have the same direction, it is combinatorially decidable whether the framework is infinitesimally rigid or not. Also, in order to prove that, we present a new forest-partition theorem.

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 non-crossing Laman frameworks, on a given set of n points in the plane. 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 the constrained non-crossing Laman frameworks on a given point set is connected by flips which preserve the Laman property.

Voronoi diagrams 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. In this paper we are interested in various measures associated with criteria on goodness of an input line segment with respect to each point in the plane as the "point of view." These measures basically show how well a segment or information displayed on the segment can be seen from the point. Mathematically, the measures are defined in terms of the shapes of the triangle determined by the point and the line segment. We study the combinatorial and algorithmic complexities of those Voronoi diagrams. We also study an associated optimization problem: find a point that maximizes the smallest measure value over the measures with respect to all the given line segments. We give sufficient conditions for an optimal point to lie on a Voronoi edge and present a heuristic optimization algorithm for those measures having this property.

Property management (PM) service has been becoming the essential service for office buildings in the age of building stocks. In this study, we investigate how PM affects the rent of office buildings. 51 office buildings which are of small and middle scale in Shinbashi Area are selected for analysis. Criteria based on "kansei" judgment (the subjective judgment) of evaluators are proposed as the basis of evaluating the degree of maintenance and upgrade. Their values are derived by the field work and are integrated into the ordinary building specification and site environment data. Decision tree and rent prediction analyses are carried out. Through these analyses, we will show findings such that standard deviations of kansei judgment which are roughly discretized are important factors for rent prediction, and so on.

A non-crossing geometric graph is a graph embedded on a given set of points in the plane with non-crossing straight line segments. In this paper we present a new general framework for enumerating non-crossing geometric graphs for a given point set. By applying our idea to specific enumeration problems, we obtain faster algorithms for enumerating plane straight-line graphs, non-crossing spanning connected graphs, non-crossing spanning trees and non-crossing minimally rigid frameworks. Furthermore, we also obtain efficient enumeration algorithms for non-crossing geometric graph classes, for which no enumeration algorithm has been reported so far, such as non-crossing matchings, non-crossing blue-and-red matchings, non-crossing k-vertex or k-edge connected graphs or non-crossing directed spanning trees. The proposed idea is relatively simple, and can be potentially applied to various other enumeration problems of non-crossing geometric graphs.

Given a directed graph D = (V,A) with a root s epsilon V such that a non-negative rational weight is associated with each are in A, we consider the problem for finding a set of minimum weight k spanning in-trees rooted at s which cover A. Here the weight of k spanning in-trees is defined as the sum of weights of all arcs contained in these in-trees. We will show that this problem can be solved in polynomial time. For this, we first consider the set of linear inequalities in R-A that coincides with the convex hull P-ic(D) of a |A|-dimensional positive integral vector x such that we can cover A by k spanning in-trees rooted at s such that e epsilon A is contained in x(e) in-trees where R represents the set of reals. After this, we will show that the separation problem for this polytope can be solved in polynomial time, which implies the polynomial time solvability of the minimum weight in-tree cover problem in conjunction with the ellipsoid method. Furthermore, we will consider the generalization of the minimum in-tree cover problem such that the input directed graph has multiple roots. Although this problem is still open, we give the generalization of the result presented by Vidyasankar[13] which is used to derive the set of linear inequalities which determine P-ic (D) to the case of the multiple roots.

Iii this paper we will investigate the relationship between the room layout which is mainly 3LDK type and the rent of apartment in the Suburb of Kyoto City by extracting meaningful substructures of a graph representing the room layout using a graph mining algorithm and emerging patterns. We will then construct a prediction model for the rent of apartments with high accuracy. Through our analysis, we will reveal certain typical substructures in the room layout which strongly affect the rent.

Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider the following generalized geometric spanner problem under L, distance: Given a set of disjoint objects S, find a spanning network G with minimum size so that for any pair of points in different objects of S, there exists a path in G with length no more than t times their L, distance, where t is the stretch factor. Specifically, we focus on three types of objects: rectilinear segments, axis aligned rectangles, and rectilinear monotone polygons. By combining ideas of t-weekly dominating set, walls, aligned pairs and interval cover, we develop a 4-approximation algorithm (measured by the number of Steiner points) for each type of objects. Our algorithms run in near quadratic time, and can be easily implemented for practical applications.

Given a directed graph D = (V, A) with a set of d specified vertices S = {s(1), ... , s(d)} subset of V and a function f : S -> Z(+) where Z(+) denotes the set of non-negative integers, we consider the problem which asks whether there exist Sigma(d)(i=1) f(s(i)) in-trees denoted by T-i,T-1,T-i,T-2, ... , T-i,T-f(si) for every i = 1, ... , d such that T-i,T-1,T-i,T-2, ... , T-i,T-f(si) are rooted at si, each T-i,T-j spans vertices from which s(i) is reachable and the union of all arc sets of T-i,T-j for i = 1, ... , d and j = 1, ... , f (s(i)) covers A. In this paper, we prove that such set of in-trees covering A can be found by using an algorithm for the weighted matroid intersection problem in time bounded by a polynomial in Sigma(d)(i=1) f(s(i)) and the size of D. Furthermore, for the case where D is acyclic, we present another characterization of the existence of in-trees covering A, and then we prove that in-trees covering A can be computed more efficiently than the general case by finding maximum matchings in a series of bipartite graphs.

For a given convex polygon with inner angle no less than 2/3 pi and boundary edge bounded by [l, alpha l] for 1 <= alpha <= 1.4, where l is a given standard bar's length, we investigate the problem of triangulating the polygon using some Steiner points such that (i) the length of each edge in triangulation is bounded by [beta l, 2l], where beta is a given constant and meets 0 < beta <= 1/2, and (ii) the number of non-standard bars in the triangulation is minimum. This problem is motivated by practical applications and has not been studied previously. In this paper, we present a heuristic to solve the above problem, which is based on the heuristic to generate a triangular mesh with less number of non-standard bars and shorter maximal edge length, and a process to make the length of each edge lower bounded. Our procedure is simple and easily implemented for this problem, and we prove that it has good performance guaranteed. (c) 2007 Elsevier B.V. All rights reserved.

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 determination of whether a newly launched consumer product should be allowed to continue in a highly competitive market. The system is designed to overcome a shortcoming-the inability to capture multivariate interactions-of traditional decision methods. We apply the proposed method to an instant noodle sales data set that contains 38 million transactions, and compare results across several methods. (C) 2007 Elsevier B.V. All rights reserved.

This paper proposes a method for discriminating roof types and determining roof ridges from aerial images. Observing that according to the slope change of a roof surface its brightness changes, our method first approximates the histogram of brightness distribution as a smooth curve. We then extract effective characteristic variables to develop a discrimination model for classifying roof types into deck roof and inclined roof. For the roofs which are classified as inclined ones, we develop a method for classifying them into hip roofs and gables after extracting additional explanatory variables obtained by applying multiple regression to 3-dimensional brightness distribution. We finally applied the model to aerial image of residential area in Kyoto city, and observed that the classification ability of our proposed method was quite high.

Using spatial data mining techniques, we analyze car-related crimes such as auto theft, auto parts theft, and breaking into a car in the area of Nishikyo-ku, Kyoto City. The strategy of natural surveillance proposed by Crime Prevention Through Environmental Design (CPTED) is taken into consideration as visibility attributes. From the viewpoint of risk discovery, we do not employ ordinary association rule but a new data mining technique called Emerging Patterns (EPs). EP is defined as an itemset whose support increases significantly from one dataset to another. Since a large number of EPs are generated in general as in association rule, it is difficult to identify the critical factors which affect crime occurrences. Therefore, we will introduce two new ideas (a) appropriately aggregating several EPs with high growth-rate and (b) identifying a pair of similar patterns A and B such that A is not associated with high crime occurrences while B is highly correlated with crime occurrences. Finding such similar patterns reveals that the attribute value which is in B but not in A is then identified as a critical factor which arouses crimes when combined with certain factors. © 2007 - IOS Press and the authors.

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. In this paper we are interested in various measures associated with criteria on goodness of an input line segment with respect to each point in the plane as the "point of view". These measures basically show how the segment or information displayed on the segment can be seen from the point. Mathematically, the measures are defined in terms of the shape of the triangle determined by the point and the line segment. Given any such measure, we can define a Voronoi diagram for a set of line segments. In this paper we are interested in investigating their common combinatorial and structural properties. We investigate conditions for those measures to define regular Voronoi diagrams and also conditions that local optima on the measures lie only on Voronoi edges, not in the proper interior of Voronoi regions.

In this paper we will investigate the relationship between room layout and the rent of apartments by extracting meaningful substructures of a graph representing the room layout using a graph mining algorithm. We will then construct a prediction model for the rent of apartments with high accuracy. Through our analysis, we will reveal certain typical substructures in the room layout which strongly affect the rent.

Geometric spanner is a fundamental structure in computational geometry and plays an important role in many geometric networks design applications. In this paper, we consider a generalization of the classical geometric spanner problem (called segment spanner): Given a set S of disjoint 2-D segments, find a spanning network G with minimum size so that for any pair of points in S, there exists a path in G with length no more than t, times their Euclidean distance. Based on a number of interesting techniques (such as weakly dominating set, strongly dominating set, and interval cover), we present an efficient algorithm to construct the segment spanner. Our approach first identifies a set of Steiner points in S, then construct a point spanner for them. Our algorithm runs in O (vertical bar Q vertical bar + n(2) log n) time, where Q is the set of Steiner points. We show that Q is an O(1)-approximation in terms of its size when S is relatively "well" separated by a constant. For arbitrary rectilinear segments under L-1 distance, the approximation ratio improves to 2.

In this paper we present an algorithm for enumerating without repetitions all non-crossing geometric spanning trees on a given set of n points in the plane under edge inclusion constraints (i.e., some edges are required to be included in spanning trees). We will first prove that a set of all edge-constrained non-crossing spanning trees is connected via remove-add flips, based on the constrained smallest indexed triangulation which is obtained by extending the lexicographically ordered triangulation introduced by Bespamyatnikh. More specifically, we prove that all edge-constrained triangulations can be transformed to the smallest indexed triangulation among them by O(n(2)) times of greedy flips. Our enumeration algorithm generates each output graph in O(n(2)) time and O(n) space based on reverse search technique.

In this paper, we consider the evacuation problem for a network which consists of a directed graph with capacities and transit times on its arcs. This problem can be solved by the algorithm of Hoppe and Tardos [1] in polynomial time. However their running time is high-order polynomial, and hence is not practical in general. Thus it is necessary to devise a faster algorithm for a tractable and practically useful subclass of this problem. In this paper, we consider a dynamic network with a single sink s such that (i) for each vertex v the sum of transit times of arcs on any path from v to s takes the same value, and (ii) for each vertex v the minimum v-s cut is determined by the arcs incident to s whose tails are reachable from v. We propose an efficient algorithm for this network problem. This class of networks is a generalization of the grid network studied in the paper [2].

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.

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. Customers are located on nodes of the tree, and each customer has a positive demand of pickup and/or delivery. Demands of customers are served by a fleet of identical vehicles with unit capacity. Each vehicle can serve pickup and delivery demands. 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. In each tour, a vehicle begins at the depot with certain amount of goods for delivery, visits a subset of the customers in order to deliver and pick up goods and returns to the depot. At any time during the tour, a vehicle must always satisfy the capacity constraint, i.e., at any time the sum of goods to be delivered and that of goods that have been picked up is not allowed to exceed the vehicle capacity. We propose a 2-approximation algorithm for the problem. (c) 2006 Elsevier B.V. All rights reserved.

We propose the prediction models which tell who will really purchase an apartment from among those who visit a model room, and analyze the characteristic of purchase based on data-mining technique. The data of questionnaire collected from those who visited model rooms usually has a lot of missing values. In order to improve the precision of prediction, the original data is converted to the one and two dimensional probability data concerning purchase. This data conversion technique is applied to the data which an estate agent in Kansai owns. Decision-tree and logistic regression are applied in order to obtain prediction models. Precisions of three different data types: original categorical data, one dimensional probability data and two-dimensional one are compared. As a result of experiment, the followings are observed: 1. two dimensional probability data with logistic regression has the highest precision through different data, 2. customers having high purchase probability do not answer the questionnaire too much.

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 0(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.

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 problem in such a way that points are inserted one by one with uniformity preserved at every instance. Our criterion for uniformity is to minimize the gap ratio (which is the maximum gap over the minimum gap) at every point insertion. We present a linear time algorithm for finding an optimal n-point sequence with the maximum gap ratio bounded by 2([n/2]/([n/2]+1)) in the 1-dimensional case. We describe how hard the same problem is for a point set in the plane and propose a local search heuristics for finding a good solution.

We consider the problem of triangulating an x-monotone polygon with a small number of different edge lengths using Steiner points. Given a parameter alpha, where 0 &lt; alpha &lt; 1, we shall present an algorithm for finding an almost uniform triangular mesh with 3 pi/8 alpha(2) + o(1/alpha(2)) different edge lengths such that every edge length is between l and (2 + root 2 alpha)l. Experiments demonstrate the effectiveness of this algorithm.