Naoki Katoh

For a given x-monotone polygonal curve each of whose edge lengths is between l__- and 2l__-, 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__- and βl__-, where β is a given parameter satisfying 1≦β≦2. Our first algorithm computes an approximate polygonal curve using fixed square grid points in O((n/α^4) log (n/α)) time. Based on this, our second algorithm finds an approximate polygonal curve as well as an optimal grid placement simultaneously in O((n^3/α^<12>) log^2(n/α)) time, where α 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 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.

The purpose of the this research is to develop the cost planning system to be used step by step during the production process on construction projects of public offices. The purposes of the research are as follows. 1)System development for cost planning to achieve business decisions. 2)Improvement for traditional cost planning system by public clients. 3)System development for change order and Value Engineering clarified predictable construction costs. 4)System development to reduce workloads for estimating construction costs.

Generating triangular meshes using some Steiner points is one of the fundamental problems in computational geometry. We are interested in the problem of triangulating a simple polygon with a small number of different edge lengths. An algorithm is presented for finding almost uniform triangular mesh with a constant number of different edge lengths. We give a theoretical guarantee and experimental evaluation of this algorithm.

For a given convex polygon with inner angle no less than 2/3 pi and boundary edge bounded by [1, alpha l] for 1 <= alpha <= 1.4, where 1 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, and (ii) the number of non-standard bars in the triangulation 2 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 more number of 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.

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 minsum criteria with respect to L1- and L2-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.

Given a hypergraph H=(V,F) and a [0, l]-valued vector a∈[0,1]^V, its global rounding is a binary (i.e.,{0, l}-valued) vector a∈{0,l}^Vsuch that |Σ_<V∈F>(a(v)-α(v))|<1 holds for each F ∈ 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.

MUSASHI is a set of commands that 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 data mining oriented CRM systems based on MUSASHI, which are integrated with the marketing tools and data mining technology. Everybody can construct useful CRM systems at extremely low cost by introducing MUSASHI.

MUSASHI is a set of commands that 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 data mining oriented CRM systems based on MUSASHI, which are integrated with the marketing tools and data mining technology. Everybody can construct useful CRM systems at extremely low cost by introducing MUSASHI.

Information Extraction from semistructured data becomes more and more important. In order to extract meaningful or interesting contents from semistructured data, we need to extract common structured patterns from semistructured data. A tag tree pattern is an edge labeled tree with ordered children which has tree structures of tags and structured variables. An edge label is a tag, a keyword or a wildcard, and a variable can be substituted by an arbitrary tree. In particular, a contractible variable matches any subtree including a singleton vertex. A tag tree pattern is hence suited for representing common tree structured patterns in irregular semistructured data. We present a new method for extracting characteristic tag tree patterns from irregular semistructured data by using an algorithm for finding a least generalized tag tree pattern explaining given data. We report some experiments of applying this method to extracting characteristic tag tree patterns from HTML/XML files.

In this paper we introduce a KDD system called MUSASHI developed by our group It supports the entire KDD process efficiently and effectively based on data in XML format by providing a set of commands each of which performs a single function MUSASHI can be used independently without other RDBMS technology or KDD software We can efficiently handle large data (more than 4 gigabytes with 20 million records) on a standard PC Using MUSASHI, we have succeeded in discovery of useful business knowledge based on a huge amount of real business data provided by several companies

In this paper we introduce a KDD system called MUSASHI developed by our group. It supports the entire KDD process efficiently and effectively based on data in XML format by providing a set of commands each of which performs a single function. MUSASHI can be used independently without other RDBMS technology or KDD software We can efficiently handle large data (more than 4 gigabytes with 20 million records) on a standard PC. Using MUSASHI, we have succeeded in discovery of useful business knowledge based on a huge amount of real business data provided by several companies.

Optimized region rules developed by Fukuda et al. [9, 10] are effective tools for data mining in databases with numeric data. However, there are two drawbacks in the previous methods: (1) each rule can contain at most two numeric conditional attributes, and (2) the decision is made based only on whether a given data is inside or outside a region R, but not on the exact position of the data. In this paper, we propose a new method for removing these drawbacks. Indeed, by applying graph algorithmd, we give optimized numeric association rules with more than two attributes, and give layered-structure numeric association rules. Our method is also applicable to removal of exceptional data and data clustering.

This paper presents an approximation algorithm for a vehicle routing problem on a tree-shaped network with a single depot. 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., the sum of goods to be delivered and those picked up should satisfy the vehicle capacity. We propose a 2-approximation algorithm for the problem.

Digital halftoning is a technique to convert a continuous-tone image into a binary image consisting of black and white dots. It is an important technique for printing machines and printers to output an image with few intensity levels or colors which looks similar to an input image. The purposes of this paper are to reveal that there are a number of problems related to combinatorial and computational geometry and to present some solutions or clues to those problems.