加藤 直樹

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 triangulation or to an edge that crosses it. This theorem also holds for the triangles of the triangulations and in general independence systems. As an application, we give some lower bounds for the minimum-weight triangulation which can be computed in polynomial time by matching and network-flow techniques. We exhibit an easy-to-recognize class of point sets for which the minimum-weight triangulation coincides with the greedy triangulation.

This paper deals with the problem of detecting every line component, a set of edge points close enough to some line, in an N x N digital image. For this purpose, the Hough transform, which is based on voting in the dual plane, is widely used. However, there have been few theoretical studies on the relationship between its computational complexity and ability of detecting straight line components. In this paper we present two different algorithms for detecting every line component contained in a digital image. The one, which is effective in the case of a dense digital image, is based on a new transformation named L(1)-dual transform defined by the L(1)-distance between points and lines. Using concepts from number theory we can show that this algorithm finds every line component in O(N-4) time, where the size of the image is O(N-2). The other, which is effective when the edge density is low, attains efficiency by using the plane sweep technique common in computational geometry. Furthermore, we present an efficient approximation algorithm which can detect at least alpha x 100% of any line component and show that its computational complexity depends on the value of alpha. Choosing alpha = 0.5, for example, the time complexity of the algorithm is reduced from O(N-4) to O(N-3 log N). In practical-applications it is sometimes required to detect line components of width greater than one. We also present an algorithm for detecting such bold lines of specified width in the same computational complexity as above.

Given a connected undirected multigraph with n vertices and m edges, we first propose a new unifying heuristic approach to approximately solving the minimum cut and the s-t minimum cut problems by using efficient algorithms for the corresponding minimum range cut problems. Our method is based on the association of the range value of a cut and its cut value when each edge weight is chosen uniformly randomly from the Bred interval. Our computational experiments demonstrate that this approach produces very good approximate solutions. We shall also propose an O(log(2) n) time parallel algorithm using O(n(2)) processors on an arbitrary CRCW PRAM model for the minimum range cut problems, by which we can efficiently obtain approximate minimum cuts in poly-log time using a polynomial number of processors.

We study the problem of enumerating k farthest pairs for n points in the plane and the problem of enumerating k closest/farthest bichromatic pairs of n red and n blue points in the plane. We propose a new technique for geometric enumeration problems which iteratively reduces the search space by a half and provides efficient algorithms. As applications of this technique, we develop algorithms, using higher order Voronoi diagrams, for the above problems, which run in O(min{n(2), n log n + k(4/3) log n/log(1/3) k}) time and O(n + k(4/3)/log(1/3) k + k log n) space for general L(p) metric with p not equal 2, and O(min{n(2), n log n + k(4/3)}) time and O(n + k(4/3) + k log n) space for L(2) metric. For the problem of enumerating k closest/farthest bichromatic pairs; we shall also discuss the case where we have different numbers of red and blue points. To the authors 'knowledge, no nontrivial algorithms have been known for these problems and our algorithms are faster than trivial ones when k = o(n(3/2)).

In this paper we investigate the upper bounds on the numbers of transitions of minimum and maximum spanning trees (MinST and MaxST for short) for linearly moving points. Here, a transition means a change on the combinatorial structure of the spanning trees. Suppose that we are given a set of n points in d-dimensional space, S = {p1, p2, ..., p(n)}, and that all points move along different straight lines at different but fixed speeds, i.e., the position of p(i) is a linear function of a real parameter t. We investigate the numbers of transitions of MinST and MaxST when t increases from -infinity to +infinity. We assume that the dimension d is a fixed constant. Since there are O(n2) distances among n points, there are naively O(n4) transitions of MinST and MaxST. We improve these trivial upper bounds for L1 and L(infinity) distance metrics. Let kappa(p)(n) (resp. K(p)(n)) be the number of maximum possible transitions of MinST (resp. MaxST) in L(p) metric for n linearly moving points. We give the following results in this paper: kappa1(n) = O(n5/2alpha(n)), kappa(infinity)(n) = O(n5/2alpha(n)), K1(n) = THETA(n2), and K(infinity)(n) = THETA(n2) where alpha(n) is the inverse Ackermann's function. We also investigate two restricted cases, i.e., the c-oriented case in which there are only c distinct velocity vectors for moving n points, and the case in which only k points move.

Let G = (V, E) be an undirected graph with n vertices and m edges such that a real-valued weight, denoted by w(e), is associated with each edge e. This paper studies what we call the minimum range cut problem that asks to find a cut in G such that the range of all edge weights in the cut is minimum. Here, the range of a cut C is defined to be the maximum difference among weights of edges in the cut, i.e., max(eis-an-element-ofc) w(e) - min(eis-an-element-ofc) w(e). This paper proposes an O(m + n log n) algorithm for the minimum range cut problem. It is also shown that this running time is optimal. We also study two variants of this problem. One is the minimum range target cut problem. Given a prespecified value called a target, this problem asks to find a cut with minimum range among all cuts such that the target value is between the minimum and maximum of weights of edges in the cut. The second is the minimum range s - t cut problem that asks to find an s - t cut with minimum range. This paper proposes O(m + n log n) algorithms for these problems. For the second problem, we show that an ancestor tree of O(n) space recently developed by Cheng and Hu effectively represents all pairs minimum range cuts, which can be constructed in O(n2) time, and enables us to answer any minimum range s - t cut query in O(1) time [resp., in O(n) time] if we want to obtain only the range value of the cut (resp., the bipartition of vertices induced by the cut). (C) 1994 John Wiley & Sons, Inc.

Let G = (V, E) be an undirected graph with m edges and n vertices such that each edge e has a real valued weight w(e). Let MST(G) be a minimum spanning tree in G. Let f(G) be the weight of a minimum spanning tree of G if G is connected; otherwise f(G) = infinity. We define a most vital edge with respect to a minimum spanning tree in a connected undirected graph G as an edge e such that f(G - e) greater-than-or-equal-to f(G - e') for every edge e' in G. In this paper, we give O(m + n log n) and O(ma(m, n)) time algorithms, which improve O(m log m) and O(n2) time bounds by Hsu et al. in Inform. Process. Lett. 39 (1991) 277-281.

A graph-theoretical model is presented for scheduling the transmission of messages in a computer network. A related wiring problem is also discussed; connections with classical edge colorings are exhibited and optimality properties are discussed.

Let MC stand for a class of logs (i.e., sequences of read/write steps) that are serializable when multiple versions of the data items are maintained in the database. In this paper we propose a new type of multiversion cautions scheduler for database concurrency control, which dynamically imposes serialization constraints, consisting of all rw(read-write)-constraints and a subset of other serialization constraints that is dynamically determined. We shall show that (i) the key step of our scheduler is carried out by checking the acyclicity of a certain directed graph, and hence can be done in polynomial time, (ii) this scheduler achieves a higher degree of concurrency than any existing cautious schedulers such as MCS(MWW) and MCS(MWRW), if concurrency is measured in terms of their fixed point sets, and (iii) it exhibits neither cancellation nor augmentation anomaly. It is also shown that our scheduler immediately grants all write requests.

Consider a game between teams A and B, consisting of a sequence of matches, where each match takes place between one player i from A and one player j from B. Given the probability that player i wins over player j, we investigate optimal strategies on how to choose a player for the next match, for the following two types of team games. The first type assumes that after each match, the loser is eliminated from the list of remaining players, while the winner remains in the list. The team from which all players are eliminated loses the game. Assuming the Bradley-Terry model as the probability model, we first show that the winning probability does not depend on the strategy chosen. It is also shown that the Bradley-Terry model is essentially the only model for which this strategy independence holds. The second type of game assumes that both players are eliminated after each match. In this case, it is shown that choosing a player with equal probability is an optimal strategy in the sense of maximizing the expected number of wins of matches, provided that information about the order of players in the other teams is not available. The case in which a team knows the ordering of the other team is also studied.

This paper presents a survey on bicriteria network optimization problems. When there are two conflicting criteria that evaluate the solution. the bicriteria optimization is to find a solution for which these criteria are both acceptably satisfied. Standard approaches to these problems are to combine these two criteria into an aggregated single criterion. Among such problems, this paper first deals with the case in which the aggregated objective function, denoted h(f1(x), f2(x)), is convex in original two objectives f1(x) and f2(x), and, as its special case. it reviews a strongly polynomial algorithm for the bicriteria minimum-cost circulation problem. It then discusses the case in which h is concave and demonstrates that a parametric approach is effective for this case. Several interesting applications in network optimization that belong to this class are also introduced. Finally we deal with the minimum range problems which seek to find a solution such that weights of the components used in the solution are most uniform. We shall present efficient algorithms for solving these problems arised in network optimization.

Suppose that we are given a finite set E, a family of feasible subsets of E and a nonnegative cost and a reliability associated with each element in E. This paper considers the problem of finding a feasible subset such that the cost-reliability ratio of the subset is minimum among all feasible subsets. This paper first exhibits a parametric characterization of an optimal solution of this problem. Based on this characterization, it is shown that if one can solve in polynomial time the problem of finding a feasible subset that minimizes the sum of costs in the subset, it is possible to construct a fully polynomial time approximation scheme for the above minimum cost-reliability ratio problem.

This paper considers a sharing problem of distributing a given quantity of resources to a set of demand nodes in a network as equally as possible. We study the case in which the resources are of two distinct kinds and propose a polynomial time algorithm for it by reducing the problem to the one-commodity sharing problem.

This paper presents a one‐version cautious scheduler with version selection control CS1(WRW1±) which is an extension of a recently proposed single‐version cautious scheduler CS(WRW). The set of schedules that our scheduler CS1(WRW1±) accepts without delay properly includes the one that CS(WRW) does without delay. It is shown also that our CS1 (WRW1±) is free from cancellation anomaly and runs in polynomial time. Copyright © 1989 Wiley Periodicals, Inc., A Wiley Company