記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：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

掲載種別：研究論文（学術雑誌）   出版者・発行元：Springer Science and Business Media LLC  

DOI： 10.1007/s00453-013-9804-1

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

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

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：日本オペレーションズ・リサーチ学会  

近年,小中学生の登下校時を狙った事件,事故が多発している.そのため,集団で下校することで安全を確保することが重要視されてきている.年度の初めに集団下校の班分けをする作業は生徒数が少なければ,それほど手間ではないかもしれない.しかし,生徒数が少なくても突発的な事件や事故の際に,通れない地域や道路が出現するなど下校経路に制約ができてくると,それに応じた班分けを考えるのはそう簡単なことではない.また,新入生が多い大規模な学校における年度初めの班分けは生徒の家の位置だけではなく,様々な要素を考慮して行われるであろうが,そのような作業時にも,ある程度の班分けの案があると作業がしやすいと考えられる.そこで,生徒の家と学校の位置情報と道の安全性から,集団下校の経路と集団を決定する手法を提案し,計算機実験によって解の検証を行った.

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学  

CiNii Books

researchmap

その他リンク： http://hdl.handle.net/2433/140731

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：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

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：日本応用数理学会  

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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：電子情報通信学会  

量子通信路容量の代表的なものであるHolevo容量を計算する問題について, これまでのアルゴリズムと違い, 近似精度及び問題インスタンスの難しさに応じて計算時間が適応的に変わる外近似切除平面法に基づく近似アルゴリズムを与える.

CiNii Books

researchmap

記述言語：日本語   掲載種別：研究論文（研究会，シンポジウム資料等）   出版者・発行元：電子情報通信学会  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（学術雑誌）  

researchmap

記述言語：日本語   掲載種別：研究論文（研究会，シンポジウム資料等）   出版者・発行元：電子情報通信学会  

researchmap

記述言語：英語   出版者・発行元：Taylor and Francis  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Swiss Federal Institeute of Technology  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：電子情報通信学会  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：日本応用数理学会  

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

記述言語：日本語   出版者・発行元：京都大学  

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：World-Scientific  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学数理解析研究所  

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ACM  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学数理解析研究所  

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：日本応用数理学会  

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

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学  

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Gesellschaft fur Angewandte Mathematik und Mechanik  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）  

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学  

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：情報処理学会  

計算幾何学の分野では、近年、動的な対象物に対する研究が盛んになってきている。本稿では、平面上を動く集合に対する高次のVoronoi図（高次の動的Voronoi図）を求めるアルゴリズムとその解析を行う。点の座標は１つのパラメタに関する多項式や有理式で表されており、その次数が点の数によらない定数である場合を考える。ｓの動き方を決める多項式や有理式によって定まる定数としたとき、ｍ次（ｍ≧2）のVoronoi図の場合，その位柏変化の回数はO(n 2ms+m+3(n) ) であり、O(n 2ms+m+2(n) Iog n) 時間でm次の動的Voronoi図が構成できることを示す。ここで、s（n）は（n、s）Davenport?Schinzel列の最大長を表し、nに関して線形に近い関数である。また、対応の与えられた平面上の2つの点集含を回転や平行移動などの幾何的な変換によって最適な位置に当てはめる問題に、高次の動的Voronoi図が応用できることについても述べる。

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（研究会，シンポジウム資料等）  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Springer-Verlag  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：North-Holland  

Web of Science

researchmap

記述言語：日本語   掲載種別：研究論文（研究会，シンポジウム資料等）  

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学  

CiNii Books

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学  

CiNii Books

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学  

CiNii Books

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学  

CiNii Books

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：日本応用数理学会  

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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：National Tsing Hua University  

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学  

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：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

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ASSOC COMPUTING MACHINERY  

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：CCCG Organizing Committee  

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学  

CiNii Books

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：情報処理学会  

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ASSOC COMPUTING MACHINERY  

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Springer-Verlag  

Web of Science

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Kinokuniya  

DOI： 10.1007/BF03167907

Scopus

researchmap

記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：ACM  

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：電子情報通信学会  

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：京都大学  

CiNii Books

researchmap

記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Kinokuniya  

DOI： 10.1007/BF03167752

Scopus

researchmap

記述言語：日本語   掲載種別：研究論文（学術雑誌）   出版者・発行元：津田塾大学  

CiNii Books

researchmap

総ページ数：677頁   担当ページ：104-178,425-531   記述言語：日本語   著書種別：学術書

researchmap

担当ページ：131-157   記述言語：日本語   著書種別：学術書

researchmap

総ページ数：215頁   担当ページ：1-49   記述言語：日本語   著書種別：学術書

researchmap

総ページ数：726頁   担当ページ：457-462   記述言語：日本語   著書種別：事典・辞書

researchmap

総ページ数：445   記述言語：日本語   著書種別：学術書

researchmap

記述言語：日本語   著書種別：学術書

researchmap

総ページ数：1316頁   記述言語：日本語   著書種別：事典・辞書

researchmap

総ページ数：518頁   担当ページ：211頁～337頁を担当.   記述言語：日本語   著書種別：学術書

researchmap

総ページ数：340頁   担当ページ：132頁～220頁を担当.   記述言語：日本語   著書種別：学術書

researchmap

記述言語：日本語   掲載種別：書評論文，書評，文献紹介等   出版者・発行元：近代科学社 地理情報処理学会  

researchmap

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：サイエンス社  

CiNii Books

researchmap

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：岩波書店 日本応用数理学会  

DOI： 10.11540/bjsiam.9.1_84

researchmap

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：サイエンス社  

CiNii Books

researchmap

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：サイエンス社  

CiNii Books

researchmap

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：サイエンス社  

CiNii Books

researchmap

記述言語：日本語   掲載種別：会議報告等   出版者・発行元：日本応用数理学会  

researchmap

記述言語：日本語   掲載種別：書評論文，書評，文献紹介等   出版者・発行元：日本応用数理学会  

researchmap

記述言語：日本語   出版者・発行元：一般社団法人情報処理学会  

非負整数の列S=（_1，s_2，…，s_）がグラフ的であるとは、それを次数列としてもつようなグラフが存在することであり、グラフ次数列問題とは、与えられた非負整数列S=（_1，s_2，…，s_）に対して、Sがグラフ的であるかどうかを判定し、もしそうならば、Sを次数列としてもつグラフを構成する問題である。本論文では、各種のグラフ次数列問題を考え、効率的アルゴリズムを与える。A sequence of nonnegative integers S=(s_1,s_2,…,s_n) is graphical if there is a graph with vertices υ_1,υ_2,…,υ_n such that deg(υ_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 algorithm.

CiNii Books

researchmap

記述言語：日本語   掲載種別：書評論文，書評，文献紹介等   出版者・発行元：情報処理学会  

researchmap

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：日本オペレーションズ・リサーチ学会  

researchmap

記述言語：日本語  

多角形配置問題とは,与えられた多角形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

記述言語：日本語  

本論文では，与えられた凸多角形Pを他の多角形Qの内部に最適に，すなわち，PとQの相対Euclid距離が最小になるように配置する問題を考える。P?Euclid Voronoi図と呼ばれる新しいVoronoi図を定義し，その動的な変化を考える事により，種々の問題に効率の良い算法が得られる。特に，Pがm角形，Qがn角形のときに，Pを回転と平行移動で動かす時，O（^4nλ_<16>（）log )時間で最適配置が求まる。ここでλ_<16>（）は，N文字の16次Davenport?Shinzel列の長さで，ほとんど線形な関数である。更に，Pがk個の連結成分を持ち，平行移動する場合も取り扱う。This paper considers the maximin placement of a convex polygon P inside a polygon Q, and introduce 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^4nλ_<16>(mn)log mn) time, where m and n are the numbers of edges of P and Q, respectively, and λ_<16>(N) is the maximum length of Davenport-Schinzel sequences on N alphabets of order 16. The problem of placing multiple translates of P inside Q in a maximin manner is also considered, an in connection with this problem the dynamic Voronoi diagram of k rigidly moving sets of n points is investigated.

CiNii Books

researchmap

記述言語：日本語   掲載種別：記事・総説・解説・論説等（その他）   出版者・発行元：共立出版  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：ポスター発表  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：ポスター発表  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（招待・特別）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（招待・特別）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（招待・特別）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（招待・特別）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：公開講演，セミナー，チュートリアル，講習，講義等  

researchmap

記述言語：英語  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（招待・特別）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：英語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap

記述言語：日本語   会議種別：口頭発表（一般）  

researchmap