Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Springer Verlag  

In the air-traffic control, the information related to each air-plane needs to be always displayed as the label. Motivated by this appli-cation, de Berg and Gerrits (Comput. Geom. 2012) presented free-label maximization problem, where the goal is to maximize the number of intersection-free labels. In this paper, we introduce an alternative label-ing problem for the air-traffic control, called point-overlap minimization. In this problem, we focus on the number of overlapping labels at a point in the plane, and minimize the maximum among such numbers. Instead of maximizing the number of readable labels as in the free-label maximiza-tion, we here minimize the cost required for making unreadable labels readable. We provide a 4-approximation algorithm using LP rounding for arbitrary rectangular labels and a faster combinatorial 8-approximation algorithm for unit-square labels.

DOI： 10.1007/978-3-319-57586-5_28

Scopus

researchmap

Publishing type：Research paper (scientific journal)   Publisher：Springer Science and Business Media LLC  

DOI： 10.1007/s00453-013-9804-1

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

We consider the minimum maximal matching problem, which is NP-hard (Yannakakis and Gavril (1980) [18]). Given an unweighted simple graph G = (V, E), the problem seeks to find a maximal matching of minimum cardinality. It was unknown whether there exists a non-trivial approximation algorithm whose approximation ratio is less than 2 for any simple graph. Recently, Z. Gotthilf et al. (2008) [5] presented a (2 - c log vertical bar V vertical bar/vertical bar V vertical bar) approximation algorithm, where c is an arbitrary constant.
In this paper, we present a (2 - 1/X'(G))-approximation algorithm based on an LP relaxation, where X'(G) is the edge-coloring number of G. Our algorithm is the first non-trivial approximation algorithm whose approximation ratio is independent of vertical bar V vertical bar. Moreover, it is known that the minimum maximal matching problem is equivalent to the edge dominating set problem. Therefore, the edge dominating set problem is also (2 - 1/X'(G)-approximable. From edge-coloring theory, the approximation ratio of our algorithm is 2 - 1/Delta(G)+1, where Delta(G) represents the maximum degree of G. In our algorithm, an LP formulation for the edge dominating set problem is used. Fujito and Nagamochi (2002) [4] showed the integrality gap of the LP formulation for bipartite graphs is at least 2 - 1/Delta(G). Moreover, X'(G) is Delta(G) for bipartite graphs. Thus, as far as an approximation algorithm for the minimum maximal matching problem uses the LP formulation, we believe our result is the best possible. (C) 2011 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.ipl.2011.02.006

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

We consider totally unimodularity for edge-edge adjacency matrices which represent a relationship between two edges in a graph. The matrices appear in integer programming formulations for the minimum maximal matching problem and the edge dominating set problem. We consider a problem of characterizing graphs having totally unimodular matrices as their edge-edge adjacency matrices, and give a necessary and sufficient condition for the characterization. The condition is the first characterization for edge-edge adjacency matrices. © 2011 Springer-Verlag.

DOI： 10.1007/978-3-642-22685-4_32

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

The bisector of two nonempty sets P and Q in R-d is the set of all points with equal distance to P and to Q. A distance k-sector of P and Q, where k >= 2 is an integer, is a (k - 1)-tuple (C-1, C-2 ..... Ck-1) such that C-i is the bisector of Ci-1 and Ci+1 for every i = 1.2 ..... k - 1, where C-0 = P and C-k = Q. This notion, for the case where P and Q are points in R-2, was introduced by Asano, Matousek, and Tokuyama, motivated by a question of Murata in VLSI design. They established the existence and uniqueness of the distance 3-sector in this special case. We prove the existence of a distance k-sector for all k and for every two disjoint, nonempty, closed sets P and Q in Euclidean spaces of any (finite) dimension (uniqueness remains open), or more generally, in proper geodesic spaces. The core of the proof is a new notion of k-gradation for P and Q, whose existence (even in an arbitrary metric space) is proved using the Knaster-Tarski fixed point theorem, by a method introduced by Reem and Reich for a slightly different purpose. (C) 2010 Elsevier B.V. All rights reserved.

DOI： 10.1016/j.comgeo.2010.05.001

Web of Science

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ASSOC COMPUTING MACHINERY  

The bisector of two nonempty sets P and Q in R(d) is the set of all points with equal distance to P and to Q. A distance k-sector of P and Q, where k >= 2 is an integer, is a (k - 1)-tuple (C(1),C(2), ... , C(k-1)) such that C(i) is the bisector of C(i-1) and C(i+1) for every i = 1, 2, ... , k - 1, where C(0) = P and C(k) = Q. This notion, for the case where P and Q are points in R(2), was introduced by Asano, MatouSek, and Tokuyama, motivated by a question of Murata in VLSI design. They established the existence and uniqueness of the distance 3-sector in this special case. We prove the existence of a distance k-sector for all k and for every two disjoint, nonempty, closed sets P and Q in Euclidean spaces of any ( nite) dimension (uniqueness remains open), or more generally, in proper geodesic spaces. The core of the proof is a new notion of k-gradation for P and Q, whose existence (even in an arbitrary metric space) is proved using the Knaster-Tarski xed point theorem, by a method introduced by Reem and Reich for a slightly di erent purpose.

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCI LTD  

Anisotropic mesh generation is important for interpolation and numerical modeling. Recently, Labelle and Shewchuk proposed a two-dimensional guaranteed-quality anisotropic mesh generation algorithm called a Voronoi refinement algorithm. This algorithm treats only domains with straight lines as inputs. In many applications, however, input domains have many curves and the exact representation of curves is required for efficient numerical modeling. In this paper, we extend the Voronoi refinement algorithm and propose it as a guaranteed-quality anisotropic mesh generation algorithm for domains with curved boundaries. Some experimental results are also shown. (C) 2008 Elsevier Ltd. All rights reserved.

DOI： 10.1016/j.cad.2008.08.010

Web of Science

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：京都大学  

CiNii Books

researchmap

Other Link： http://hdl.handle.net/2433/140731

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer  

We show some coincidences of Voronoi diagrams in a quantum state space with respect to some distances. This means a computational geometry interpretation of a structure of a quantum state space. More properly, we investigate the Voronoi diagrams with respect to the divergence, Fubini-Study distance, Bures distance, geodesic distance and Euclidean distance. As an application of it, we explain an effective algorithm tocompute the Holevo capacity of one-qubit quantum channel. The effectiveness of the algorithm is supported by the coincidence of Voronoi diagrams. Moreover, our result provides insights into the applicability of the same method to a higher level system. © 2009 Springer-Verlag Berlin Heidelberg.

DOI： 10.1007/978-3-540-85126-4_4

Scopus

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer  

We show some coincidences of Voronoi diagrams in a quantum state space with respect to some distances. This means a computational geometry interpretation of a structure of a quantum state space. More properly, we investigate the Voronoi diagrams with respect to the divergence, Fubini-Study distance, Bures distance, geodesic distance and Euclidean distance. As an application of it, we explain an effective algorithm tocompute the Holevo capacity of one-qubit quantum channel. The effectiveness of the algorithm is supported by the coincidence of Voronoi diagrams. Moreover, our result provides insights into the applicability of the same method to a higher level system. © 2009 Springer-Verlag Berlin Heidelberg.

DOI： 10.1007/978-3-540-85126-4_4

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE COMPUTER SOC  

In this paper, we incorporate the concept of differentiability into Voronoi diagrams. We consider the influence area diagrams consisting of areas with differentiable boundaries. The diagram is called a curved Voronoi diagram. Any level of differentiability can be used in the definition of the curved Voronoi diagram depending on its applications. One of the applications is path planning for car-like robots in an area with obstacles. Car-like robots can easily drive along a path consisting of clothoid curve segments, circular arcs, and line segments. Therefore, we discuss a method for constructing a clothoid curve, circle, and line (CCL) diagram.

Web of Science

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：日本応用数理学会  

In this paper, we consider a path planning problem for a car-like robot with nonholonomic constraints in motion planning. The path should be smooth and the steering angle has to change continuously. Various techniques have been proposed. However, those methods vary the angular velocity or they do not give a consideration to obstacles in the work space. We propose a new method of finding a path by the Voronoi graph and the clothoid curve which has uniform angular velocity. By using the obtained path, the robot can move smoothly and avoid collision with the obstacles as far as possible.

DOI： 10.11540/jsiamt.16.4_631

CiNii Books

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

The label placement problem is one of the most important problems in geographic information systems, cartography, graph drawing, and graphical interface design. In this paper, we considered the label size maximization problem for points with axes-parallel rectangular labels that correspond to character strings and have different widths based on the number of characters. We propose an algorithm for computing the optimum size for the label size maximization problem in the 2-position model and a polynomial time algorithm for the problem in the 4-position model. Our algorithm cannot obtain the maximum value in the 4-position model because the label size maximization problem in the 4-position model is NP-hard. However, our algorithm is efficient in practice, as shown by computational experiments. Further, computational results for JR trains, subways and major private railroads in Tokyo are presented.

DOI： 10.1093/ietfec/e89-a.4.1035

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：IEEE Computer Society Press  

For one-qubit pure quantum states, it is already proved that the Voronoi diagrams with respect to two distances -Euclidean distance and the quantum divergence - coincide. This fact is a support for a known method to calculate the Holevo capacity. To consider an applicability of this method to quantum states of a higher level system, it is essential to check if the coincidence of the Voronoi diagrams also occurs. In this paper, we show a negative result for that expectation. In other words, we mathematically prove that those diagrams no longer coincide in a higher dimension. That indicates that the method used in one-qubit case to calculate the Holevo capacity might not be effective in a higher dimension. © 2006 IEEE.

DOI： 10.1109/ISVD.2006.27

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：電子情報通信学会  

CiNii Books

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)   Publisher：電子情報通信学会  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

The label placement problem is one of the most important problems in geographic information systems, cartography, graph drawing and graphical interface design. In this paper, we consider the problem of labeling points and curves in maps drawn from digital data. In digital maps, a curve is represented as a set of points and consists of many small segments. The label for each curve must be placed alongside the corresponding curve. We define a continuous labeling space for points and curves, and present an algorithm using this space for positioning labels. Computational results for subway and JR train maps in Tokyo are presented.

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)   Publisher：電子情報通信学会  

researchmap

Language：English   Publisher：Taylor and Francis  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER-VERLAG BERLIN  

For a set S of n points in the plane, a Manhattan network on S is a geometric network G(S) such that, for each pair of points in S, G(S) contains a rectilinear path between them of length equal to their distance in the L-1-metric. The minimum Manhattan network problem is a problem of finding a Manhattan network of minimum length. Gudmundsson, Levcopoulos, and Narasimhan proposed a 4-approximation algorithm and conjectured that there is a 2-approximation algorithm for this problem. In this paper, based on a different approach, we improve their bound and present a 2-approximation algorithm.

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：Swiss Federal Institeute of Technology  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：電子情報通信学会  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

This paper reports computational results of a new approach of analyzing network reliability against probabilistic link failures. This problem is hard to solve exactly when it is large-scale, which is shown from complexity theory, but the approach enables us to analyze networks of moderate size, as demonstrated by our experimental results. Furthermore, this approach yields a polynomial-time algorithm for complete graphs, whose reliability provides a natural upper bound for simple networks, and also leads to an efficient algorithm for computing the dominant part of the reliability function when the failure probability is sufficiently small. Computational results for these cases are also reported. This approach thus establishes a fundamental technology of analyzing network reliability in practice.

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：OPERATIONS RES SOC JAPAN  

This paper considers the maximin placement of a convex polygon P inside a polygon Q, and introduces several new static and dynamic Voronoi diagrams to solve the problem. It is shown that P can be placed inside Q, using translation and rotation, so that the minimum Euclidean distance between any point on P and any point on Q is maximized in O(m(4)n lambda(16)(mn) log mn)time, where m and n are the numbers of edges of P and Q, respectively, and lambda(16)(N) is the maximum length of Davenport-Schinzel sequences on N alphabets of order 16. If only translation is allowed, the problem can be solved in O(mn log mn) time. The problem of placing multiple translates of P inside Q in a maximin manner is also considered.

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

This paper formulates problems of fitting two corresponding sets of points by translation, rotation and scaling, and proposes efficient algorithms for the fitting. The algorithms are based on the theory of lower envelopes, or Davenport-Schinzel sequences, and linearization techniques in computational geometry, and are related to dynamic furthest Voronoi diagrams.

Web of Science

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：日本応用数理学会  

The Jones polynomial is an invariant in knot theory. It is known that the Jones polynomial of an alternating link is related to the Tutte polynomial in graph theory. Here, it is shown that the new algorithm [11] of computing the Tutte polynomial can be applied to computing the Jones polynomial of an arbitrary link. Although a problem of computing the Jones polynomial is #P-hard, by using the planarity it can be calculated for some large links, say a link whose signed plane graph is a 10 × 10 grid graph and which has 180 crossings. A new result for the case where a knot is represented as a braid is also given.

DOI： 10.11540/jsiamt.8.3_341

CiNii Books

researchmap

Language：Japanese  

CiNii Books

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：GORDON BREACH SCI PUBL LTD  

A weighted geometric fitting problem between two corresponding sets of points is to minimize the maximum weighted distance between two corresponding pairs of points by translating and rotating one set to the other set. For this weighted geometric fitting-problem, dynamic weighted Voronoi diagrams have been applied to obtain an almost cubic algorithm. In this paper, we show a new reduction of the problem to the two-dimensional Davenport-Schinzel sequences, and provide a much simpler proof for the almost cubic bound. The technique used for this purpose can be applied to more general cases.

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：World-Scientific  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：京都大学数理解析研究所  

CiNii Books

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER-VERLAG BERLIN  

This paper considers the problem of computing a minimum weight triangulation of n points in the plane, which has been intensively studied in recent years in computational geometry. This paper investigates a branch-and-cut approach for minimum weight triangulations. The problem can be formulated as finding a minimum-weight maximal independent set of intersection graphs of edges. In combinatorial optimization, there axe known many cuts for the independent set problem, and we further use a cut induced by geometric properties of triangulations. Combining this branch-and-cut approach with the beta -skeleton method, the moderate-size problem could be solved efficiently in our computational experiments. Polyhedral characterizations of the proposed cut and applications of another old skeletal approach in mathematical programming as the independent set problem are also touched upon.

Web of Science

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：京都大学数理解析研究所  

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：日本応用数理学会  

Triangulations have been one of main topics in computational geometry and other fields in recent years. In the planar case, any pair of triangulation can be transformed to each other by a sequence of so-called Delaunay flips, and enumeration of all triangulations can be done by reverse search. However, there is no known result for higher-dimensional triangulations. Recently, some types of triangulations have been found to bridge geometric issues and algebraic ones. Regular triangulations are of such a type, and form a meaningful wide subclass of triangulations of points in general dimensions. Especially, regular triangulations have a close connection with discriminants of polynomials in several variables. Restricting ourselves to the class of regular triangulations in any dimensions, we know that such triangulations correspond to vertices of some polytope, and we can enumerate all regular triangulations by reverse search.

DOI： 10.11540/bjsiam.6.1_29

CiNii Books

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

CiNii Books

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：AKADEMIE VERLAG GMBH  

This paper reports on algorithmic results for the enumeration of regular triangulations of a set V of n points given in a (d - 1)-demensional affine space. Regular triangulations form a subclass of triangulations and have mathematical and application-related importance. For example, for higher dimensional spaces, i.e., d > 3, it is never a trivial task to generate every triangulation, but by concentrating on this subclass of regular triangulations, it becomes possible to enumerate all members of this subclass even, in higher dimensional cases. In this paper, we first describe regular triangulations and related mathematical problems, and then summarize the algorithmic results obtained so far. Some computational results are also touched upon.

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Gesellschaft fur Angewandte Mathematik und Mechanik  

researchmap

Language：English   Publishing type：Research paper (scientific journal)  

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：Kyoto University  

CiNii Books

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：IEICE-INST ELECTRONICS INFORMATION COMMUNICATIONS ENG  

A sequence of nonnegative integers S - (s1, s2, ..., s(n)) is graphical if there is a graph with vertices v1, v2, ..., v(n) such that deg(v(i)) = s(i) for each i = 1, 2, ..., n. The graphical degree sequence problem is: Given a sequence of nonnegative integers, determine whether it is graphical or not. In this paper, we consider several variations of the graphical degree sequence problem and give efficient algorithms.

Web of Science

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：情報処理学会  

The Voronoi diagrams for moving objects have been investigated in computational geometry. We extend the concept of the higher-order Voronoi diagram for n points in the plane to the one for the case that the coordinates are represented by polynomials or rational functions of a parameter. We show that the combin_atorial complexity of this m-th higher-order dynamic Voronoi diagram is O(n^2λ_<s+m+3>(n)) and this diagram can be constructed in O(n^2mλ_<s+m+2>(n)log n) time, where s some fixed number determined by the degree of the parameter functions and λ_s(n) is the maximum length of (n,s) Davenport Schinzel sequence. Applications of the higher-order dynamic Voronoi diagram to geometric fitting problems are also touched upon.

CiNii Books

researchmap

Language：English   Publishing type：Research paper (conference, symposium, etc.)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Springer-Verlag  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：ELSEVIER SCIENCE BV  

Let S = { s1,s2,..., s(n)} be a set of sites in E(d), where every site s(i) has a positive real weight omega(i). This paper gives algorithms to find weighted orthogonal L(infinity) and L1 approximating hyperplanes for S. The algorithm for the weighted orthogonal L1 approximation is shown to require O(n(d)) worst-case time and O(n) space for d greater-than-or-equal-to 2. The algorithm for the weighted orthogonal L(infinity) approximation is shown to require 0(n log n) worst-case time and 0(n) space for d = 2, and O(n(right perpendicular d/2 + 1 left perpendicular)) worst-case time and 0(n(right perpendicular (d + 1)/2 left perpendicular)) space for d &gt; 2. In the latter case, the expected time complexity may be reduced to O(n(right perpendicular (d + 1)/2 left perpendicular)). The L(infinity) approximation algorithm can be modified to solve the problem of finding the width of a set of n points in E(d), and the problem of finding a stabbing hyperplane for a set of n hyperspheres in E(d) with varying radii. The time and space complexities of the width and stabbing algorithms are seen to be the same as those of the L(infinity) approximation algorithm.

Web of Science

researchmap

Language：Japanese   Publishing type：Research paper (conference, symposium, etc.)  

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：Kyoto University  

CiNii Books

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

CiNii Books

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

CiNii Books

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：日本応用数理学会  

Recently, the Voronoi diagram for moving objects has been investigated in connection with motion planning in robotics and geometric optimization problems in computational geometry. In this paper, we consider the Voronoi diagram for moving points parametrized by t in the plane, whose coordinates are polynomials or rational functions of t. We show that the dynamic Voronoi diagram has the combinatorial complexity of O(n^2λ_<s+2>(n)) and can be computed in O(n^2λ_<s+1>(n)log n) time and O(n) space, where s is some fixed number and λ_s(n) is the maximum length of (n, s) Davenport-Schinzel sequence.

DOI： 10.11540/jsiamt.1.2_127

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

CiNii Books

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：National Tsing Hua University  

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：Kyoto University  

CiNii Books

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)  

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Kinokuniya  

It has already been proved that the linear operator defined in (1.1) has eigenvalues (1-α)n (n=0, 1, 2,...), which are all simple, and a multiple eigenvalue 0, and that the eigenfunction qn(x) corresponding to the eigenvalue (1-α)n is a polynomial of degree n. In this paper we give a mathematical proof to the conjecture, which has been based on numerical computation, that qn(x) tends tocossin(πx/α) as n→∞, and that the convergence of qn(x) tocossin(πx/α) is linear. The proof makes use of a generating function technique. © 1990 JJAM Publishing Committee.

DOI： 10.1007/BF03167842

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ASSOC COMPUTING MACHINERY  

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：CCCG Organizing Committee  

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)  

CiNii Books

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：Information Processing Society of Japan (IPSJ)  

CiNii Books

CiNii Research

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：情報処理学会  

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ASSOC COMPUTING MACHINERY  

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：SPRINGER  

Web of Science

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Kinokuniya  

The sequence of random variables:Xn=α[Un+(1-α)Un-1+...+(1-α)n-2U2+ (1-α)n-1U1] (0&lt
α&lt
1
Ui: independent random variables subject to the uniform distribution on [-1, 1]
n=1, 2, ...) has been shown to have a nonanalytic C∞-function as the limit probability density function. We shall analyze, in a constructive manner, the spectral structure of the operators related to the functional equation defining that function and its derivatives, and show that those functions can be characterized by the property that they constitute the family orthogonal to a family of polynomials on [-1, 1]. © 1988 JJAM Publishing Committee.

DOI： 10.1007/BF03167907

Scopus

researchmap

Language：English   Publishing type：Research paper (international conference proceedings)   Publisher：ACM  

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：電子情報通信学会  

CiNii Books

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Kyoto University  

CiNii Books

researchmap

Language：English   Publishing type：Research paper (scientific journal)   Publisher：Kinokuniya  

It is shown that the probability density function pn(x) for the random variable Xn = α[Un + (1 - α)Un - 1 + ... + (1 - α)n - 2U2 + (1 - α)n - 1U1] (where 0&lt
α&lt
1 and Ui′s are independent random variables subject to the uniform distribution on the interval [-1, 1]) uniformly converges to an infinitely differentiable function p∞(x) as n→∞, and that p∞(x) is nonanalytic at infinitely many points. In particular, for α=1/2, p∞(x) is nowhere analytic on [-1, 1]. © 1987 JJAM Publishing Committee.

DOI： 10.1007/BF03167752

Scopus

researchmap

Language：Japanese   Publishing type：Research paper (scientific journal)   Publisher：津田塾大学  

CiNii Books

researchmap

Total pages：677頁   Responsible for pages：104-178,425-531   Language：Japanese   Book type：Scholarly book

researchmap

Responsible for pages：131-157   Language：Japanese   Book type：Scholarly book

researchmap

Total pages：215頁   Responsible for pages：1-49   Language：Japanese   Book type：Scholarly book

researchmap

Total pages：726頁   Responsible for pages：457-462   Language：Japanese   Book type：Dictionary, encyclopedia

researchmap

Total pages：445   Language：Japanese   Book type：Scholarly book

researchmap

Language：Japanese   Book type：Scholarly book

researchmap

Total pages：1316頁   Language：Japanese   Book type：Dictionary, encyclopedia

researchmap

Total pages：518頁   Responsible for pages：211頁～337頁を担当.   Language：Japanese   Book type：Scholarly book

researchmap

Total pages：340頁   Responsible for pages：132頁～220頁を担当.   Language：Japanese   Book type：Scholarly book

researchmap

Language：Japanese   Publishing type：Book review, literature introduction, etc.   Publisher：近代科学社 日本オペレーションズ・リサーチ学会  

CiNii Books

researchmap

Language：Japanese   Publishing type：Book review, literature introduction, etc.   Publisher：近代科学社 地理情報処理学会  

researchmap

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (other)   Publisher：サイエンス社  

CiNii Books

researchmap

Language：Japanese   Publisher：東京 : 電子情報通信学会  

CiNii Books

CiNii Research

researchmap

Other Link： http://id.ndl.go.jp/bib/4759970

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (other)   Publisher：岩波書店 日本応用数理学会  

DOI： 10.11540/bjsiam.9.1_84

researchmap

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (other)   Publisher：サイエンス社  

CiNii Books

researchmap

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (other)   Publisher：サイエンス社  

CiNii Books

researchmap

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (other)   Publisher：サイエンス社  

CiNii Books

researchmap

Language：Japanese   Publisher：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

CiNii Research

researchmap

Language：Japanese   Publishing type：Meeting report   Publisher：日本応用数理学会  

researchmap

Language：Japanese   Publisher：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

CiNii Research

researchmap

Language：Japanese   Publishing type：Book review, literature introduction, etc.   Publisher：日本応用数理学会  

researchmap

Language：Japanese   Publisher：Information Processing Society of Japan (IPSJ)  

A sequence of nonnegative integers S=(s_1, s_2,..., s_n) is graphical if there is a graph with vertices v_1, v_2,..., v_n such that deg(v_i)=s_i for each i=1, 2, ..., n. The graphical degree sequence problem is: Given a sequence S of nonnegative integers, determine whether it is graphical and, if so, construct a graph having S as a degree sequence. In this paper, we consider several variations of the graphical degree sequence problem and give efficient algorithms.

CiNii Books

researchmap

Language：Japanese   Publishing type：Book review, literature introduction, etc.   Publisher：情報処理学会  

researchmap

Language：Japanese   Publisher：公益社団法人日本オペレーションズ・リサーチ学会  

CiNii Books

CiNii Research

researchmap

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (other)   Publisher：日本オペレーションズ・リサーチ学会  

researchmap

Language：Japanese  

多角形配置問題とは,与えられた多角形Pを他の多角形Qの内部に配置するという問題である.この問題は,モーションプラニングとも密接に関係があり,いろいろな面から研究がなされている.本稿では,何種類かのEuclid距離をもちいた多角形max-imin配置問題を考える.最も基本的なmaximin配置問題は,Pの任意の点とQの任意の点のEuclid距離の最小値が最大となるように凸多角形Pを多角形Qの内部に配置するという問題である.さらに,Pをいくつか一直線上に並ぶようにして,同様のmaximin配置問題を解くことも考える.直感的にいえば,多角形PまたはそのいくつかのコピーをQの境界からなるべく離れるようにQの内部に置く問題を考えることであると言ってよい.似たような問題に,Pに相似な最大の多角形をQの内部に配置するという問題があり,これについてはFortune[F]やChewとKedem[CK]で考察されている.しかし,彼らは凸距離関数を用いており,Euclid距離を用いた問題については,これまでに研究がなされていない.ここでは,新しいVoronoi図(P-Euclid Voronoi図と呼ぶ)を定義することによってこれらのmaximin配置問題に対する効率の良いアルゴリズムを紹介し,それらの組合せ的複雑度についての解析を行なう.計算複雑度の解析においては,Davenport-Schinzel列の理論を用いる.凸多角形の多角形内への配置問題は,地図の中へ地名などを記入するときにも現われる.このような場面では,文字列は長方形で表わされ,領域は多角形で表現される.長方形を,上記の意味でのmaximin問題の解となるように多角形の内部に置きたい.また,文字列を1つの長方形として捕らえるのではなく,すでに置かれている文字と重ならないように,かつ,一定の間隔で一列に並ぶように各文字を置くことを考える。このような問題を解くためには,穴のある多角形の内部に正方形のコピーを一定の間隔で配置する問題を考える必要がある。本稿で扱うmaximin配置問題と得られた結果,また,それに関連してすでに得られている結果をまとめると次のようになる.Pはm個の辺を持つ凸多角形,Qはn個の辺を持つ多角形(または多角形領域)とする.[figure] (P1)平行移動だけを用いてPの任意の点とQの任意の点とのEuclid距離の最小値が最大となるように凸多角形Pを多角形領域Qの内部に置く.問題(P1)は,平行移動によりPの相似な図形のうち最大のものをQの内部に配置する問題と関係が深い.Pの相似な図形で最大のものを配置する問題についてはPに関する凸距離関数に対するQのVoronioi図を用いてO(mnlogmn)の手間で解ける([F]).(P1)もO(mmlogmn)の手間で解ける([AIIT]}).(P2)回転と平行移動によってPの任意の点とQの任意の点とのEuclid距離の最小値が最大になるように凸多角形Pを多角形領域Q内に配置せよ.(P2)はO(m^4λ_<16>(mn)logmn)の手間で解くことができる.ここで,λ_<16>(mn)は位数16のDavenport-Schinzel列の最大長を表わす.一般に,λ_δ(N)はNにほとんど線形な関数であることがわかっている.(P3)Q内にPのk個のコピーを次のように配置する.Pのコピーは水平線上に並び,コピー間の距離hと、Pの任意の点とQの任意の点の間の距離の最小値が最大となるようにする.ここで,hは与えられた定数h_0>0以上であるような変数である.k=2とk≥3の場合にそれぞれ問題(P3)は,O(m^2n^2logmn),O(k^6m^3n^3logkmn)の手間で解ける.

CiNii Books

researchmap

Language：Japanese  

CiNii Books

researchmap

Language：Japanese   Publishing type：Article, review, commentary, editorial, etc. (other)   Publisher：共立出版  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Poster presentation  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Poster presentation  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (invited, special)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Public lecture, seminar, tutorial, course, or other speech  

researchmap

Language：English  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (invited, special)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：English   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap

Language：Japanese   Presentation type：Oral presentation (general)  

researchmap