2024/08/22 更新

写真a

イマイ ケイコ
今井 桂子
IMAI Keiko
所属
理工学部 教授
その他担当機関
理工学研究科情報工学専攻博士課程前期課程
理工学研究科電気・情報系専攻博士課程後期課程
連絡先
メールによる問い合わせは《こちら》から
外部リンク

学位

  • 理学博士 ( 津田塾大学 )

学歴

  • 1985年3月
     

    津田塾大学   理学研究科   数学専攻   博士後期   単位取得満期退学

経歴

  • 2017年4月 - 2023年3月

    中央大学高等学校   校長

  • 1999年4月 -  

    中央大学   理工学部情報工学科   教授

  • 1992年4月 - 1999年3月

    中央大学   理工学部情報工学科   助教授

  • 1990年4月 - 1992年3月

    津田塾大学   学芸学部数学科   研究助手

  • 1988年4月 - 1990年3月

    九州工業大学   情報科学センター   助手

  • 1988年2月 - 1988年3月

    東京大学   工学部計数工学科   助手

  • 1985年4月 - 1988年2月

    東京大学   工学部計数工学科   教務職員

▼全件表示

所属学協会

  • 情報処理学会

  • 日本応用数理学会

  • 電子情報通信学会

  • 日本数学会

  • 日本オペレーションズ・リサーチ学会

  • 地理情報システム学会

  • Association for Computing Machinery

▼全件表示

研究キーワード

  • 情報学

研究分野

  • 情報通信 / 情報学基礎論  / 情報学基礎理論

論文

  • Automatic drawing of complex metro maps

    Masahiro Onda, Masaki Moriguchi, Keiko Imai

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   E104A ( 9 )   1150 - 1155   2021年

     詳細を見る

    記述言語:英語   掲載種別:研究論文(国際会議プロシーディングス)   出版者・発行元:Institute of Electronics Information Communication Engineers  

    The Tokyo subway is one of the most complex subway networks in the world and it is difficult to compute a visually readable metro map using existing layout methods. In this paper, we present a new method that can generate complex metro maps such as the Tokyo subway network. Our method consists of two phases. The first phase generates rough metro maps. It decomposes the metro networks into smaller subgraphs and partially generates rough metro maps. In the second phase, we use a local search technique to improve the aesthetic quality of the rough metro maps. The experimental results including the Tokyo metro map are shown.

    DOI: 10.1587/transfun.2020DMP0019

    Scopus

    researchmap

  • Minimum point-overlap labelling 査読

    Yuya Higashikawa, Keiko Imai, Takeharu Shiraga, Noriyoshi Sukegawa, Yusuke Yokosuka

    Optimization Methods and Software   36 ( 2-3 )   316 - 325   2020年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Taylor & Francis Online  

    DOI: 10.1080/10556788.2020.1833880

    researchmap

  • Extended formulations of lower-truncated transversal polymatroids 査読

    Hiroshi Imai, Keiko Imai, Hidefumi Hiraishi

    Optimization Methods and Software   2020年7月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Taylor & Francis Online  

    DOI: 10.1080/10556788.2020.1769619

    researchmap

  • Automatic Drawing for Tokyo Metro Map 査読

    Masahiro Onda, Masaki Moriguchi, Keiko Imai

    Proceedings of the European Workshop on Computational Geometry   2018年3月

     詳細を見る

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

    researchmap

  • Polynomial time algorithms for label size maximization on rotating maps 査読

    Yusuke Yokosuka, Keikoi Imai

    Journal of Information Processing   25   572 - 579   2017年8月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元:Information Processing Society of Japan  

    Map labeling is the problem of placing labels at corresponding graphical features on a map. There are two main optimization problems: the label number maximization problem and the label size maximization problem. In general, both problems are NP-hard for static maps. Recently, the widespread use of several applications, such as personal mapping systems, has increased the importance of dynamic maps and the label number maximization problem for dynamic cases has been studied. In this paper, we consider the label size maximization problem for points on rotating maps. Our model is as follows. For each label, an anchor point is chosen inside the label or on its boundary. Each label is placed such that the anchor point coincides with the corresponding point on the map. Furthermore, while the map fully rotates from 0 to 2π, the labels are placed horizontally according to the angle of the map. Our problem consists of finding the maximum scale factor for the labels such that the labels do not intersect, and determining the placing of the anchor points. We describe an O(n log n)-time and O(n)-space algorithm for the case where each anchor point is inside the label. Moreover, if the anchor points are on the boundaries, we also present an O(n log n)-time and O(n)-space exact and approximation algorithms for several label shapes.

    DOI: 10.2197/ipsjjip.25.572

    Scopus

    researchmap

  • 多視点ワイヤーアートの生成と最適化

    鈴木 廉, 森口 昌樹, 今井 桂子

    精密工学会学術講演会講演論文集   2017   583 - 584   2017年

     詳細を見る

    記述言語:日本語   出版者・発行元:公益社団法人 精密工学会  

    本研究では,二つの線画を,それぞれ異なる視点位置ごとにワイヤーを用いて実現するワイヤーアートの生成を行う.二つの線画と二つの視点位置を入力,ワイヤーフレームを出力とする.出力となるワイヤーフレームは連結であり,そのワイヤーフレームを直交投影法を用いて,平面上へと射影したものは入力線画に一致する.そのようなワイヤーフレームが常に存在することを示した.また最大辺長および最小辺長のワイヤーフレームを計算し,比較した.

    DOI: 10.11522/pscjspe.2017S.0_583

    researchmap

  • Minimum point-overlap labeling 査読

    Yuya Higashikawa, Keiko Imai, Yusuke Matsumoto, Noriyoshi Sukegawa, Yusuke Yokosuka

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   10236   334 - 344   2017年

     詳細を見る

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

  • On Total Unimodularity of Edge–Edge Adjacency Matrices 査読

    Yusuke Matsumoto, Naoyuki Kamiyama, Keiko Imai

    Algorithmica   67 ( 2 )   277 - 292   2013年10月

     詳細を見る

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

    DOI: 10.1007/s00453-013-9804-1

    researchmap

  • Polynomial Time Algorithms for Label Size Maximization on Rotating Maps 査読

    Yusuke Yokosuka, Keiko Imai

    Proceedings of the 25th Canadian Conference on Computational Geometry   187 - 192   2013年8月

     詳細を見る

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

    researchmap

  • An approximation algorithm dependent on edge-coloring number for minimum maximal matching problem 査読

    Yusuke Matsumoto, Naoyuki Kamiyama, Keiko Imai

    INFORMATION PROCESSING LETTERS   111 ( 10 )   465 - 468   2011年4月

     詳細を見る

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

  • On totally unimodularity of edge-edge adjacency matrices 査読

    Yusuke Matsumoto, Naoyuki Kamiyama, Keiko Imai

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   6842   354 - 365   2011年

     詳細を見る

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

    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

  • Distance k-sectors exist 査読

    Keiko Imai, Akitoshi Kawamura, Jiri Matousek, Daniel Reem, Takeshi Tokuyama

    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS   43 ( 9 )   713 - 720   2010年11月

     詳細を見る

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

  • 安全性を考慮した集団下校経路の作成 -階層型施設配置モデルの適用- 査読

    吉田祐太, 今井桂子

    オペレーションズ・リサーチ: 経営の科学   55 ( 8 )   453 - 458   2010年8月

     詳細を見る

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

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

    CiNii Books

    researchmap

  • An Approximation Algorithm Dependent on Edge-coloring Number for Minimum Maximal Matching Problem 査読

    Yusuke Matsumoto, Naoyuki Kamiyama, Keiko Imai

    Proceedings of the 13th Japan-Korea Joint Workshop on Algorithms and Computation   80 - 85   2010年7月

     詳細を見る

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

    researchmap

  • Distance k-Sectors Exist 査読

    Keiko Imai, Akitoshi Kawamura, Jiri Matousek, Daniel Reem, Takeshi Tokuyama

    PROCEEDINGS OF THE TWENTY-SIXTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY (SCG'10)   210 - 215   2010年

     詳細を見る

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

  • Guaranteed-quality anisotropic mesh generation for domains with curved boundaries 査読

    Yusuke Yokosuka, Keiko Imai

    COMPUTER-AIDED DESIGN   41 ( 5 )   385 - 393   2009年5月

     詳細を見る

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

  • 距離k分割線と一般図形のゾーン図の存在と一意性について

    今井桂子, 河村彰星, 村松悠, 徳山豪

    京都大学数理解析研究所講究録   1649   236 - 243   2009年5月

     詳細を見る

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

    CiNii Books

    researchmap

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

  • Distance k-Sectors and Zone Diagrams 査読

    Keiko Imai, Akitoshi Kawamura, Jiri Matousek, Yu Muramatsu, Takeshi Tokuyama

    Proceedings of the 25th European Workshop on Comutational Geometry   191 - 195   2009年3月

     詳細を見る

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

    researchmap

  • Computational geometry analysis of quantum state space and its applications 査読

    Kimikazu Kato, Mayumi Oto, Hiroshi Imai, Keiko Imai

    Studies in Computational Intelligence   158   67 - 108   2009年

     詳細を見る

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

  • Computational geometry analysis of quantum state space and its applications 査読

    Kimikazu Kato, Mayumi Oto, Hiroshi Imai, Keiko Imai

    Studies in Computational Intelligence   158   67 - 108   2009年

     詳細を見る

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

  • Smallest enclosing ball problem in a quantum state space and its application 査読

    Kimikazu Kato, Hiroshi Imai, Keiko Imai

    Proceedings of the 5th International Symposium on Voronoi Diagrams in Science |rn|and Engineering   123 - 132   2008年9月

     詳細を見る

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

    researchmap

  • Error Analysis of Numerical Calculation about One-Qubit Quantum Channel Capacity 査読

    Kimikazu Kato, Hiroshi Imai, Keiko Imai

    Proceedings of the 4th International Symposium on Voronoi Diagrams in Science and Engineering   276 - 281   2007年6月

     詳細を見る

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

    researchmap

  • Curved voronoi diagrams consisting of influence areas with differentiable boundaries 査読

    Yusuke Matsumoto, Keiko Imai, Hisashi Suzuki

    ISVD 2007: THE 4TH INTERNATIONAL SYMPOSIUM ON VORONOI DIAGRAMS IN SCIENCE AND ENGINEERING 2007, PROCEEDINGS   270 - 275   2007年

     詳細を見る

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

  • 多角形障害物のある領域における車両型ロボットの安全で滑らかな経路生成 査読

    松本雄介, 鈴木一平, 今井桂子

    日本応用数理学会論文誌   16 ( 4 )   631 - 649   2006年12月

     詳細を見る

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

    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

  • Voronoi Diagrams and a Numerical Estimation of a Quantum Channel Capacity 査読

    Kimikazu Kato, Mayumi Oto, Hiroshi Imai, Keiko Imai

    2nd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science   69 - 76   2006年10月

     詳細を見る

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

    researchmap

  • Label size maximization for rectangular node labels 査読

    S Toriumi, H Endo, K Imai

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E89A ( 4 )   1035 - 1041   2006年4月

     詳細を見る

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

  • Guaranteed-Quality Anisotropic Mesh Generation for Domains with Curves 査読

    Yusuke YOKOSUKA, Keiko IMAI

    European Workshop on Computational Geometry   125 - 128   2006年3月

     詳細を見る

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

    researchmap

  • On a geometric structure of pure multi-qubit quantum states and its applicability to a numerical computation 査読

    Kimikazu Kato, Hiroshi Imai, Mayumi Oto, Keiko Imai

    Proceedings - 3rd International Symposium on Voronoi Diagrams in Science and Engineering 2006, ISVD 2006   48 - 53   2006年

     詳細を見る

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

  • Voronoi Diagrams for 1-qubit Pure Quantum States 査読

    Kimikazu Kato, Mayumi Oto, Hiroshi Imai, Keiko Imai

    Proceedings of the 2nd International Symposium on Voronoi Diagrams   293 - 299   2005年10月

     詳細を見る

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

    researchmap

  • Holevo容量を求める外近似切除平面アルゴリズム

    大音真由美, 今井桂子

    電子情報通信学会論文誌   J88-A ( 8 )   922 - 925   2005年8月

     詳細を見る

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

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

    CiNii Books

    researchmap

  • 文字数を考慮したラベルサイズ最大化問題 査読

    鳥海重喜, 遠藤久雄, 今井桂子

    第18回 回路とシステム軽井沢ワークショップ論文集   625 - 630   2005年4月

     詳細を見る

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

    researchmap

  • Computational Geometry on 1-Qubit States 査読

    M. Oto, H. Imai, K. Imai

    Proceedings of the International Symposium on Voronoi Diagrams in Science and Engineering (VD 2004)   145 - 151   2004年9月

     詳細を見る

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

    researchmap

  • Map label placement for points and curves 査読

    T Kameda, K Imai

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E86A ( 4 )   835 - 840   2003年4月

     詳細を見る

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

  • Enumerating Triangulations in General Dimensions 査読

    H. Imai, T. Masada, F. Takeuchi, K. Imai

    International Journal of Computational Geometry and Applications   12 ( 6 )   455 - 480   2002年4月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    researchmap

  • 地図における点と辺に対するラベルの自動配置 査読

    亀田貴之, 今井桂子

    第15回 回路とシステム(軽井沢)ワークショップ論文集   471 - 476   2002年4月

     詳細を見る

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

    researchmap

  • GIS in Japan: Developments and Applications

    H. Imai, K. Imai, K. Inaba, K. Kubota

    Nontraditional Database System   130 - 145   2002年4月

     詳細を見る

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

    researchmap

  • An improved algorithm for the minimum Manhattan network problem 査読

    R Kato, K Imai, T Asano

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   2518   344 - 356   2002年

     詳細を見る

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

  • GIS and ITS Infrastructures in Japan-Standardization and Network-Algorithmic Applications

    H.Imai, K.Imai, K.Inaba, K.Kubota

    Proceeding of the International Workshop on Emerging Technologies for Geo-Based Applications   153 - 167   2000年5月

     詳細を見る

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

    researchmap

  • Structures of Trigangulations of Point 査読

    K.Imai

    IEICE Transactions on Information and Systems, Special Issue on Algorithm Engineering: Surverys   E83-D ( 3 )   428 - 437   2000年3月

     詳細を見る

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

    researchmap

  • Computational investigations of all-terminal network reliability via BDDs 査読

    H Imai, K Sekine, K Imai

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E82A ( 5 )   714 - 721   1999年5月

     詳細を見る

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

  • Maximin location of convex objects in a polygon and related dynamic Voronoi diagrams 査読

    K Imai, H Imai, T Tokuyama

    JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF JAPAN   42 ( 1 )   45 - 58   1999年3月

     詳細を見る

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

  • Minimax geometric fitting of two corresponding sets of points and dynamic furthest Voronoi diagrams 査読

    K Imai, S Sumino, H Imai

    IEICE TRANSACTIONS ON INFORMATION AND SYSTEMS   E81D ( 11 )   1162 - 1171   1998年11月

     詳細を見る

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

  • Jones多項式の計算 査読

    関根京子, 今井浩, 今井桂子

    日本応用数理学会論文誌   8 ( 3 )   341 - 354   1998年9月

     詳細を見る

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

    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

  • BDDによる計算代数・計算幾何の不変量計算

    今井浩, 今井桂子

    数理解析研究所講究録   1041   12 - 18   1998年4月

     詳細を見る

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

    CiNii Books

    researchmap

  • Dynamic weighted Voronoi diagrams and weighted minimax matching of two corresponding point sets 査読

    K Imai, H Imai

    OPTIMIZATION METHODS & SOFTWARE   10 ( 2 )   261 - 274   1998年

     詳細を見る

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

  • Network Reliability Computation - Theory and Practice 査読

    H.Imai, K.Sekine, K.Imai

    Information Systems and Technologies for Network Society   41 - 48   1997年9月

     詳細を見る

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

    researchmap

  • Enumerating Triangulations for Arbitrary Configurations of Points and for Products of Two Simplices

    F. Takeuchi, H. Imai, K. Imai

    数理解析研究所講究録   992   98 - 105   1997年5月

     詳細を見る

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

    CiNii Books

    researchmap

  • A branch-and-cut approach for minimum weight triangulation 査読

    Y Kyoda, K Imai, F Takeuchi, A Tajima

    ALGORITHMS AND COMPUTATION, PROCEEDINGS   1350   384 - 393   1997年

     詳細を見る

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

  • Enumeration of Regular Triangulations 査読

    T.Masada, H.Imai, K.Imai

    Proceedings of the 12th Annual ACM Symposium on Computational Geometry   224 - 233   1996年5月

     詳細を見る

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

    researchmap

  • Enumeration of Regular Triangulations

    K.Imai, H.Imai

    数理解析研究所講究録   950   126 - 132   1996年5月

     詳細を見る

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

    researchmap

  • 三角形分割と判別式、凸多面体. 査読

    今井桂子

    応用数理   6 ( 1 )   29 - 39   1996年3月

     詳細を見る

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

    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

  • 3角形分割と凸多面体

    今井浩, 今井桂子

    京都大学数理解析研究所講究録   934   149 - 166   1996年1月

     詳細を見る

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

    CiNii Books

    researchmap

  • Enumeration of regular triangulations with computational results 査読

    T Masada, K Imai, H Imai

    ZEITSCHRIFT FUR ANGEWANDTE MATHEMATIK UND MECHANIK   76   187 - 190   1996年

     詳細を見る

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

  • Enumeration of regular triangulations with computational results 査読

    T.Masada, K.Imai, H.Imai

    Third International Congress on Industrial and Applied Mathematics   124   1995年7月

     詳細を見る

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

    researchmap

  • On Weighted Dynamic Voronoi Diagrams

    Keiko Imai, Hiroshi Imai

    Snapshots of Computational and Discrete Geometry   3   268 - 277   1994年7月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)  

    researchmap

  • Discrete Geometry and Dapvenport-Schinzel Sequence

    Keiko Imai

    京都大学数理解析研究所講究録   872   65 - 78   1994年5月

     詳細を見る

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

    CiNii Books

    researchmap

  • GRAPHICAL DEGREE SEQUENCE PROBLEMS 査読

    M TAKAHASHI, K IMAI, T ASANO

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E77A ( 3 )   546 - 552   1994年3月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(学術雑誌)   出版者・発行元: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図とその応用 査読

    今井桂子, 今井浩

    情報処理学会論文誌   34 ( 12 )   2458 - 2463   1993年12月

     詳細を見る

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

    計算幾何学の分野では、近年、動的な対象物に対する研究が盛んになってきている。本稿では、平面上を動く集合に対する高次のVoronoi図(高次の動的Voronoi図)を求めるアルゴリズムとその解析を行う。点の座標は1つのパラメタに関する多項式や有理式で表されており、その次数が点の数によらない定数である場合を考える。sの動き方を決める多項式や有理式によって定まる定数としたとき、m次(m≧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

  • Discrete Geometry and its Related Problems 招待

    Keiko Imai

    Proceedings of the Fifth RAMP Symposium   113 - 126   1993年10月

     詳細を見る

    記述言語:英語   掲載種別:研究論文(研究会,シンポジウム資料等)  

    researchmap

  • Probing a set of hyperplanes by lines and related problems 査読

    Y.Aoki, H.Imai, K.Imai, D.Rappaport

    Lecture Notes in Computer Science   709   72 - 82   1993年8月

     詳細を見る

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

    researchmap

  • Orthogonal weighted linear L1 and L approximation and applications 査読

    M.E.Houle, H.Imai, K.Imai, J.-M.Robert, P.Yamamoto

    Discrete and Applied Mathematics   43 ( 3 )   217 - 232   1993年6月

     詳細を見る

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

    Web of Science

    researchmap

  • On Weighted Dynamic Voronoi Diagrams 査読

    Keiko Imai, Hiroshi Imai

    第6回 回路とシステム軽井沢ワークショップ 論文集   103 - 108   1993年4月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(研究会,シンポジウム資料等)  

    researchmap

  • Generalized Geometric Fitting Problem and Weighted Dynamic Voronoi Diagrams

    Keiko Imai, Hiroshi Imai

    京都大学数理解析研究所講究録   833   110 - 119   1993年4月

     詳細を見る

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

    CiNii Books

    researchmap

  • 超平面/曲面のアレンジメントの組合せ論的性質

    青木保一, 今井浩, 今井桂子

    京都大学数理解析研究所講究録   802   41 - 53   1992年8月

     詳細を見る

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

    CiNii Books

    researchmap

  • 高次の動的Voronoi図とその応用

    今井桂子, 今井浩

    京都大学数理解析研究所講究録   790   222 - 228   1992年6月

     詳細を見る

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

    CiNii Books

    researchmap

  • 動的な点に対するVoronoi図とその応用について 査読

    今井桂子

    日本応用数理学会論文誌   1 ( 2 )   127 - 134   1991年6月

     詳細を見る

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

    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

  • 1つの変数に関して低次の交線をもつ代数曲面のアレンジメントについて

    今井桂子, 今井浩

    京都大学数理解析研究所講究録   754   220 - 227   1991年6月

     詳細を見る

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

    CiNii Books

    researchmap

  • Voronoi diagrams for moving objects

    H.Imai, K.Imai

    Proceedings of International Computer Symposium   600 - 606   1990年12月

     詳細を見る

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

    researchmap

  • 凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図

    青沼裕美, 今井 浩, 今井桂子, 徳山 豪

    京都大学数理解析研究所講究録   731   177 - 186   1990年10月

     詳細を見る

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

    CiNii Books

    researchmap

  • A unified linear-space approach to geometric minimax problems 査読

    Tetsuo Asano, Michael E. Houle, Hiroshi Imai, Keiko Imai

    Proceedings of the 2nd Canadian Conference in Computational Geometry   20 - 23   1990年8月

     詳細を見る

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

    researchmap

  • On asymptotic properties of the eigenfunctions of a linear operator 査読

    Sigeiti Moriguti, Masao Iri, Keiko Kabaya-Imai

    Japan Journal of Applied Mathematics   7 ( 2 )   203 - 229   1990年6月

     詳細を見る

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

  • MAXIMIN LOCATION OF CONVEX OBJECTS IN A POLYGON AND RELATED DYNAMIC VORONOI DIAGRAMS 査読

    H AONUMA, H IMAI, K IMAI, T TOKUYAMA

    PROCEEDINGS OF THE SIXTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY   225 - 234   1990年

     詳細を見る

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

    Web of Science

    researchmap

  • Clustering/hashing points in the plane with maxmin criteria 査読

    T.Asano, H.Imai, K.Imai

    Proceedings of First Canadian Conference on Computational Geometry   15   1989年8月

     詳細を見る

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

    researchmap

  • 動的な点に対するVoronoi図について

    今井桂子

    京都大学数理解析研究所講究録   695   225 - 232   1989年6月

     詳細を見る

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

    CiNii Books

    researchmap

  • 点集合の重み付きミニマックス線形近似問題に対するアルゴリズム

    今井, 桂子, 今井, 浩

    情報処理学会論文誌   30 ( 4 )   544 - 546   1989年4月

     詳細を見る

    記述言語:日本語   掲載種別:研究論文(学術雑誌)   出版者・発行元:一般社団法人情報処理学会  

    d次元空間でのn点の重み付きミニマックス線形近似問題が アルゴリズム的には d+1次元での2n点の凸包を求めるという計算幾何学での最も基本的な問題に帰着できることを示す.これより d=2の平面の場合には 問題がO(n log n)の最適の手間で解けることがわかる.

    CiNii Books

    CiNii Research

    researchmap

  • 点集合間の重み付きミニマックス線形近似問題に対するアルゴリズム 査読

    今井桂子, 今井浩

    情報処理学会論文誌   30 ( 4 )   1 - 3   1989年4月

     詳細を見る

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

    researchmap

  • MINIMAX GEOMETRIC FITTING OF 2 CORRESPONDING SETS OF POINTS 査読

    K IMAI, S SUMINO, H IMAI

    PROCEEDINGS OF THE FIFTH ANNUAL SYMPOSIUM ON COMPUTATIONAL GEOMETRY   266 - 275   1989年

     詳細を見る

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

    Web of Science

    researchmap

  • Weighted orthogonal linear L approximation and applications 査読

    M.E.Houle, H.Imai, K.Imai, J.-M.Robert

    Lecture Notes in Computer Science   382   183 - 191   1989年

     詳細を見る

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

    Web of Science

    researchmap

  • On operators defining a family of nonanalytic C-functions. 査読

    K.Kabaya-Imai, M.Iri

    Japan Journal of Applied Mathematics   5 ( 3 )   333 - 365   1988年10月

     詳細を見る

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

    DOI: 10.1007/BF03167907

    Scopus

    researchmap

  • Algorithms for vertical and orthogonal L1 linear approximation of points 査読

    P.Yamamoto, K.Kato, K.Imai, H.Imai

    Proceedings of 4th Annual ACM Symposium on Computational Geometry   352 - 361   1988年6月

     詳細を見る

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

    researchmap

  • 球面上のミニマックス施設配置問題の計算複雑度 査読

    今井浩, 炭野重雄, 今井桂子

    電子情報通信学会論文誌D   J71-D ( 6 )   1155 - 1158   1988年6月

     詳細を見る

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

    CiNii Books

    researchmap

  • On orthogonal linear L_1 approximation of points

    Peter Yamamoto, Keiko Imai, Hiroshi Imai

    京都大学数理解析研究所講究録   666   275 - 284   1988年

     詳細を見る

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

    CiNii Books

    researchmap

  • Sum of uniformly distributed random variables and a family of nonanalytic C-functions. 査読

    K.Kabaya, M.Iri

    Japan Journal of Applied Mathematics   4 ( 1 )   1 - 22   1987年2月

     詳細を見る

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

    DOI: 10.1007/BF03167752

    Scopus

    researchmap

  • Low genusのcanonical curvesのgeometry 査読

    蒲谷桂子

    津田塾大学紀要   18 ( 18 )   1 - 34   1986年3月

     詳細を見る

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

    CiNii Books

    researchmap

▼全件表示

書籍等出版物

  • 理論計算機科学事典

    今井桂子( 担当: 分担執筆 範囲: 4.3 計算幾何学)

    朝倉書店  2022年1月 

     詳細を見る

    総ページ数:793   担当ページ:348-360   記述言語:日本語   著書種別:事典・辞書

    researchmap

  • 量子グラフ状態

    今井桂子( 担当: 単著)

    サイエンス社  2021年12月 

     詳細を見る

    総ページ数:100   担当ページ:58-65   記述言語:日本語  

    researchmap

  • 世界標準MIT教科書 ストラング:計算理工学

    監訳, 日本応用数理学会, 監訳幹事, 今井桂子, 岡元久|rn|訳者, 山本有作, 三井斌友, 土屋卓也, 芦野隆一, 緒方秀教, 降旗大介, 速水謙, 山下真( 担当: 監修)

    近代科学社  2017年1月 

     詳細を見る

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

    researchmap

  • 応用数理ハンドブック

    日本応用数理学会監修, 薩摩順吉, 大石進一, 杉原正顕編集( 担当: 単著)

    朝倉書店  2013年10月 

     詳細を見る

    総ページ数:685   担当ページ:542-543   記述言語:日本語  

    researchmap

  • アルゴリズム工学ー計算困難への挑戦ー

    ( 担当: 分担執筆 範囲: 地理情報処理)

    共立出版  2001年6月 

     詳細を見る

    担当ページ:226-227   記述言語:日本語   著書種別:学術書

    researchmap

  • 非線形の力学系とカオス(新装板).(S.Wiggins:Introduction to Applied Nonlinear Dynamical Systems and Chaos,1990,Springer-Verlag.)

    丹羽敏雄監訳, 今井桂子, 田中茂, 水谷正大, 森真訳( 担当: 共訳)

    シュプリンガー・フェアラーク東京  2000年6月 

     詳細を見る

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

    researchmap

  • アルゴリズムの道具箱

    戸川隼人, 有澤誠編著, 仙波一郎, 今井桂子, 茨城俊秀著( 担当: 分担執筆 範囲: 幾何図形編を担当)

    サイエンス社  2000年1月 

     詳細を見る

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

    researchmap

  • 離散構造とアルゴリズムⅥ

    藤重悟編, 今井桂子, 玉木久夫, 永持仁, 岩田覚, 福島正夫著( 担当: 分担執筆 範囲: 第1章 三角形分割全体の離散構造とその性質)

    近代科学社  1999年7月 

     詳細を見る

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

    researchmap

  • 経営科学OR用語大事典

    森村英典, 刀根薫, 伊理正夫監訳( 担当: 共訳 範囲: ネットワーク最適化)

    朝倉書店  1999年1月 

     詳細を見る

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

    researchmap

  • 組合せ幾何学のアルゴリズム(H.Edels-brunner:Algorithms in Combinatorial Geometry,1987,Sptinger-Verlag.)

    H.Edelsbrunner著, 今井浩, 今井桂子訳( 担当: 共訳)

    共立出版  1995年2月 

     詳細を見る

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

    researchmap

  • 計算幾何学

    今井浩, 今井桂子( 担当: 単著 範囲: 共同執筆につき、本人担当部分の抽出不可能.)

    共立出版  1994年10月 

     詳細を見る

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

    researchmap

  • 情報処理用語大事典.

    ( 担当: 共著 範囲: 約15000語のうち162語を担当.)

    オーム社  1992年11月 

     詳細を見る

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

    researchmap

  • 非線形の力学系とカオス(下) .(S.Wiggins : Introduction to Applied Nonlinear Dynamical Systems and Chaos, 1990, Springer-Verlag.)

    丹羽敏雄監訳, 今井桂子, 田中茂, 水谷正大, 森真訳( 担当: 共訳)

    シュプリンガー・フェアラーク東京  1992年10月 

     詳細を見る

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

    researchmap

  • 非線形の力学系とカオス(上) .(S.Wiggins : Introduction to Applied Nonlinear Dynamical Systems and Chaos, 1990, Springer-Verlag.)

    丹羽敏雄監訳, 今井桂子, 田中茂, 水谷正大, 森真訳( 担当: 共訳)

    シュプリンガー・フェアラーク東京  1992年4月 

     詳細を見る

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

    researchmap

▼全件表示

MISC

  • Polynomial Time Algorithms for Label Size Maximization on Rotating Maps

    Yusuke Yokosuka, Keiko Imai

    情報処理学会論文誌   58 ( 8 )   2017年8月

     詳細を見る

    記述言語:英語  

    Map labeling is the problem of placing labels at corresponding graphical features on a map. There are two main optimization problems: the label number maximization problem and the label size maximization problem. In general, both problems are NP-hard for static maps. Recently, the widespread use of several applications, such as personal mapping systems, has increased the importance of dynamic maps and the label number maximization problem for dynamic cases has been studied. In this paper, we consider the label size maximization problem for points on rotating maps. Our model is as follows. For each label, an anchor point is chosen inside the label or on its boundary. Each label is placed such that the anchor point coincides with the corresponding point on the map. Furthermore, while the map fully rotates from 0 to 2π, the labels are placed horizontally according to the angle of the map. Our problem consists of finding the maximum scale factor for the labels such that the labels do not intersect, and determining the placing of the anchor points. We describe an O(n log n)-time and O(n)-space algorithm for the case where each anchor point is inside the label. Moreover, if the anchor points are on the boundaries, we also present an O(n log n)-time and O(n)-space exact and approximation algorithms for several label shapes.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.572------------------------------Map labeling is the problem of placing labels at corresponding graphical features on a map. There are two main optimization problems: the label number maximization problem and the label size maximization problem. In general, both problems are NP-hard for static maps. Recently, the widespread use of several applications, such as personal mapping systems, has increased the importance of dynamic maps and the label number maximization problem for dynamic cases has been studied. In this paper, we consider the label size maximization problem for points on rotating maps. Our model is as follows. For each label, an anchor point is chosen inside the label or on its boundary. Each label is placed such that the anchor point coincides with the corresponding point on the map. Furthermore, while the map fully rotates from 0 to 2π, the labels are placed horizontally according to the angle of the map. Our problem consists of finding the maximum scale factor for the labels such that the labels do not intersect, and determining the placing of the anchor points. We describe an O(n log n)-time and O(n)-space algorithm for the case where each anchor point is inside the label. Moreover, if the anchor points are on the boundaries, we also present an O(n log n)-time and O(n)-space exact and approximation algorithms for several label shapes.------------------------------This is a preprint of an article intended for publication Journal ofInformation Processing(JIP). This preprint should not be cited. Thisarticle should be cited as: Journal of Information Processing Vol.25(2017) (online)DOI http://dx.doi.org/10.2197/ipsjjip.25.572------------------------------

    CiNii Books

    researchmap

  • 回転する地図に対するラベルサイズ最大化

    横須賀 佑介, 今井 桂子

    研究報告アルゴリズム(AL)   2013 ( 24 )   1 - 6   2013年5月

     詳細を見る

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

    ラベル配置問題とは地図中の対応する点に対して文字列やシンボルなどのラベルを配置する問題である.ラベル配置問題にはラベル数最大化問題とラベルサイズ最大化問題が存在する.一般に,これらの問題はNP-困難であることが知られている.近年,商用のGISアプリケーションにて動的な地図への重要'性が高まっており,このような背景の下,動的な地図に対するラベル数最大化問題が研究されてきた.本稿では,回転する地図に対するラベルサイズ最大化問題を扱う.この問題では,地図を0から2πの角度の間で回転させたときに,地図に対してラベルが水平であり,また,ラベル内で地図上の点と一致させる点であるアンカー点は変わらない.さらに,回転中に全てのラベルが交差しない.このような条件を満たした中で,ラベルサイズを最大化するラベルの拡大率とアンカー点を求める.我々はアンカー点がラベル内部に存在する場合のO(n log n)時間,O(n)領域アルゴリズムを提案する.提案アルゴリズムは,単位高さ(または幅)を持つラベルに対して,アンカー点がラベルの境界に存在する場合にも拡張できる.Map labeling is a problem of placing labels at the corresponding graphical features in a map. There are two optimization problems, the label number maximization problem and the label size maximization problem. In general, both problems are NP-hard for static maps. Recently, the importance of dynamic maps has been increased by several applications like personal mapping systems, and the label number maximization problem for dynamic cases has been studied. In this paper, we consider the label size maximization problem of points for rotating maps. While the map fully rotates from 0 to 2π, the labels are placed horizontally for the angle of the map such that a point called an anchor point is coincided at the corresponding point in the map. Our problem is finding the maximum scaling factor without intersection of labels and deciding the place of anchor points. We propose O(n log n)-time and O(n)-space algorithm for the case that each anchor point is inside the label. Moreover, if the labels are of unit height (or width) and the anchor points are on the boundary, we present a same time and memory bound algorithm.

    CiNii Books

    researchmap

    その他リンク: http://id.nii.ac.jp/1001/00091771/

  • Distance Trisector Curve に関する研究の誕生から発展までの経緯

    浅野 哲夫, 徳山 豪, 今井 桂子, 河村 彰星

    電子情報通信学会技術研究報告. COMP, コンピュテーション   111 ( 360 )   71 - 71   2011年12月

     詳細を見る

    記述言語:日本語  

    CiNii Books

    researchmap

  • BDDを用いたグラフのTutte多項式計算の再考察—Computing the Tutte polynomial of a graph via BDD revisited—Theoretical foundations of computing

    今井 浩, 今井 桂子, 松本 宜丈

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   108 ( 237 )   41 - 46   2008年10月

     詳細を見る

    記述言語:日本語   出版者・発行元:東京 : 電子情報通信学会  

    CiNii Books

    CiNii Research

    researchmap

    その他リンク: https://ndlsearch.ndl.go.jp/books/R000000004-I9702334

  • 最小マンハッタンネットワーク問題に対する近似アルゴリズム

    加藤亮, 今井 桂子, 浅野 孝夫

    情報処理学会研究報告アルゴリズム(AL)   2002 ( 7 )   1 - 8   2002年1月

     詳細を見る

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

    平面上に与えられたn個の点集合Sに対して、どの2点間にも2点間のL1-距離に等しい長さのパスが存在するネットワークをSのマンハッタンネットワークという.最小マンハッタンネットワーク問題は、このようなネットワークのうちで、辺の長さの総和(辺長和)が最小となるものを求める問題である.現在、この問題に対して最適解を求める多項式時間のアルゴリズムは知れておらず、既知の(多項式時間)近似アルゴリズムの最良の近似精度は4である.本論文では、この問題に対する2近似アルゴリズムを提案する。For a given set S of n points in the plane, a manhattan network for S is a network in which,for each pair of points in S, there is a path between them of length equal to their L1-distance. The minimum manhattan network problem is a problem of finding a manhattan network of minimum length. For this problem, no polynomial time exact algorithm has been known and a 4 approximation algorithm has been proposed. In this paper, we improve this bound and present a 2 approximation algorithm.

    CiNii Books

    researchmap

    その他リンク: http://id.nii.ac.jp/1001/00031997/

  • コンピュータ・ジオメトリ -計算機科学:アルゴリズムと応用

    今井桂子

    オペレーション・リサーチ   45 ( 5 )   239 - 240   2000年5月

     詳細を見る

    記述言語:日本語   掲載種別:書評論文,書評,文献紹介等   出版者・発行元:近代科学社 日本オペレーションズ・リサーチ学会  

    CiNii Books

    researchmap

  • コンピューター・ジオメトリ -計算幾何学:アルゴリズムと応用

    今井桂子

    GIS-理論と応用   8 ( 1 )   139 - 140   2000年3月

     詳細を見る

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

    researchmap

  • 結び目をほどくアルゴリズムと計算幾何

    今井桂子

    数理科学「特集:計算幾何の拡がり」   433 ( 7 )   49 - 57   1999年7月

     詳細を見る

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

    CiNii Books

    researchmap

  • 絡み目のJones多項式計算の実際

    今井 桂子, 今井 浩, 関根 京子

    電子情報通信学会技術研究報告 = IEICE technical report : 信学技報   99 ( 86 )   41 - 48   1999年5月

     詳細を見る

    記述言語:日本語   出版者・発行元:東京 : 電子情報通信学会  

    CiNii Books

    CiNii Research

    researchmap

    その他リンク: http://id.ndl.go.jp/bib/4759970

  • FORTRAN計算幾何プログラミング

    今井桂子

    日本応用数理学会学会誌   9 ( 1 )   84 - 84   1999年3月

     詳細を見る

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

    DOI: 10.11540/bjsiam.9.1_84

    researchmap

  • アルゴリズムの道具箱 -幾何図形編-(3)

    今井桂子

    Computer Today, 87   15 ( 6 )   50 - 55   1998年11月

     詳細を見る

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

    CiNii Books

    researchmap

  • アルゴリズムの道具箱 -幾何図形編-(2)

    今井桂子

    Computer Today,87   15 ( 5 )   50 - 54   1998年9月

     詳細を見る

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

    CiNii Books

    researchmap

  • アルゴリズムの道具箱 -幾何図形編-(1)

    今井桂子

    Computer Today   86 ( 4 )   40 - 45   1998年7月

     詳細を見る

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

    CiNii Books

    researchmap

  • ネットワーク信頼度計算の実際(信頼性(2))

    今井 浩, 関根 京子, 今井 桂子

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   1997   76 - 77   1997年9月

     詳細を見る

    記述言語:日本語   出版者・発行元:公益社団法人日本オペレーションズ・リサーチ学会  

    CiNii Books

    CiNii Research

    researchmap

  • 離散システム研究部会に参加して

    今井桂子

    日本応用数理学会学会誌   4 ( 4 )   85 - 86   1994年12月

     詳細を見る

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

    researchmap

  • 球面上の最適施設配置問題と動向Voronoi図(組み合わせ最適化(2))

    今井 桂子, 今井 浩

    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集   1994   118 - 119   1994年10月

     詳細を見る

    記述言語:日本語   出版者・発行元:公益社団法人日本オペレーションズ・リサーチ学会  

    CiNii Books

    CiNii Research

    researchmap

  • 計算幾何学の本から

    今井桂子

    日本応用数理学会学会誌   3 ( 2 )   69 - 70   1993年6月

     詳細を見る

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

    researchmap

  • グラフ次数列問題

    高橋 昌也, 今井 桂子, 浅野 孝夫

    情報処理学会研究報告アルゴリズム(AL)   1993 ( 48 )   111 - 118   1993年5月

     詳細を見る

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

    非負整数の列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

  • 離散構造とアルゴリズムI、藤重悟編、近代科学社.

    今井桂子

    情報処理学会学会誌   34 ( 5 )   653 - 654   1993年5月

     詳細を見る

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

    researchmap

  • 計算幾何学と並列アルゴリズム(<特集>パラレル・アルゴリズム)

    今井 浩, 今井 桂子

    オペレーションズ・リサーチ : 経営の科学   37 ( 8 )   386 - 389   1992年8月

     詳細を見る

    記述言語:日本語   出版者・発行元:公益社団法人日本オペレーションズ・リサーチ学会  

    CiNii Books

    CiNii Research

    researchmap

  • 計算幾何学と並列アルゴリズム

    今井浩, 今井桂子

    オペレーションズ・リサーチ   37 ( 8 )   32 - 35   1992年8月

     詳細を見る

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

    researchmap

  • Euclid距離による凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図

    今井 浩, 今井 桂子, 徳山 豪

    全国大会講演論文集   41   77 - 78   1990年9月

     詳細を見る

    記述言語:日本語  

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

  • Euclid距離による多角形配置問題とそれに関連する動的Voronoi図について

    今井 桂子, 徳山 豪

    情報処理学会研究報告アルゴリズム(AL)   1990 ( 37 )   1 - 8   1990年5月

     詳細を見る

    記述言語:日本語  

    本論文では,与えられた凸多角形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

  • 長方形集合の階層的表現

    今井浩, 今井桂子

    bit別冊コンピュータ・サイエンス   137 - 169   1990年5月

     詳細を見る

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

    researchmap

▼全件表示

講演・口頭発表等

  • 複数の島群に対するラベル配置アルゴリズム

    原田尚達, 今井桂子

    情報処理学会第186回アルゴリズム研究会  2022年1月  情報処理学会

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • パラメトリック曲面上の曲線メッシュ生成アルゴリズムについて

    中庭上総, 今井桂子

    情報処理学会第186回アルゴリズム研究会  2022年1月  情報処理学会

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 長方形形状の障害物をもつ領域における最短警備員巡視路

    吉野航平, 今井桂子

    2020年電子情報通信学会総合大会  2020年3月  電子情報通信学会

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 毛状表面を移動する小型軽量な二車輪駆動型ロボットの学習制御

    金沢政宏, 鈴木寿, 今井桂子

    2020年電子情報通信学会総合大会  2020年3月  電子情報通信学会

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 歩行者のいる通路におけるロボットの経路計画

    中島巧乃, 森口昌樹, 今井桂子

    情報処理学会 第80回全国大会  2018年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 折り畳んだ後の領域を考慮した三次元物体の折り畳み手法

    島津貴行, 森口昌樹, 今井桂子

    情報処理学会 第80回全国大会  2018年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 融合型シャドウアートのモデリング

    森口昌樹, 今井桂子, 杉原厚吉

    第12回錯覚ワークショップ「錯覚科学への諸アプローチとその応用」  2018年2月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Generation and Optimization of Multi-ViewWire Art 国際会議

    Ren Suzuki, Masaki Moriguchi, Keiko Imai

    Pachific Graphics 2017  2017年10月 

     詳細を見る

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

    researchmap

  • 東京の路線網に対する鉄道路線図生成手法

    恩田雅大, 森口昌樹, 今井桂子

    電子情報通信学会コンピュテーション研究部会  2017年5月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 多視点ワイヤーアートの生成と最適化

    鈴木廉, 森口昌樹, 今井桂子

    精密工学会春季大会学術講演会  2017年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 多視点ワイヤーアートの連結性と最適化

    鈴木廉, 森口昌樹, 今井桂子

    日本応用数理学会2017年研究部会連合発表会  2017年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 東京都における鉄道路線図の略地図生成とラベル配置問題

    恩田雅大, 森口昌樹, 今井桂子

    日本応用数理学会若手の会  2017年3月 

     詳細を見る

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

    researchmap

  • 東京都における鉄道路線図の略地図生成とラベル配置問題

    恩田雅大, 森口昌樹, 今井桂子

    日本オペレーションズ・リサーチ学会 都市のORワークショップ  2016年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 回転する地図に対するラベルサイズ最大化について

    横須賀祐介, 今井桂子

    電子情報通信学会コンピュテーション研究会  2016年10月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 多視点ワイヤーアートの生成

    鈴木廉, 森口昌樹, 今井桂子

    日本応用数理学会2016年度年会  2016年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 計算幾何学の地理情報処理への応用 招待

    今井桂子

    電子情報通信学会コンピュテーション研究会  2016年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(招待・特別)  

    researchmap

  • バス路線図描画手法

    篠原卓, 森口昌樹, 今井桂子

    「都市のOR」ワークショップ  2015年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 向きづけ不可能曲面のZometool近似

    坂田幸士郎, 森口昌樹, 今井桂子

    電子情報通信学会コンピュテーション研究会  2015年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 向き付け不可能曲面のZometool近似

    坂田幸士郎, 森口昌樹, 今井桂子

    日本応用数理学会2015年研究部会連合発表会  2015年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 自己交差を持つ閉曲面に対するハンドルサイクルとトンネルサイクルの計算

    藤田達也, 森口昌樹, 今井桂子

    情報処理学会アルゴリズム研究会  2015年1月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • ラベル配置における総交差数最小化問題

    尾野航平, 森口昌樹, 今井桂子

    地理情報システム学会第23回研究発表大会  2014年11月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 対角変形を用いた三角形メッシュのReebグラフ計算法

    森口昌樹, 今井桂子

    電子情報通信学会コンピュテーション研究会  2014年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 回転する地図上の正方形ラベルに対するラベルサイズ最大化

    横須賀祐介, 今井桂子

    電子情報通信学会コンピュテーション研究会  2013年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 回転する地図に対するラベルサイズ最大化

    横須賀祐介, 今井桂子

    電子情報通信学会コンピュテーション研究会  2013年5月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 回転する地図に対するラベルサイズ最大化

    横須賀祐介, 今井桂子

    都市のORスプリングセミナー  2013年4月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 指定された2点間の経路の見やすさを考慮した略地図生成

    竹内真樹, 森口昌樹, 今井桂子

    情報処理学会第75回全国大会  2013年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 複雑な路線網に対する略地図自動描画

    鈴木 泰斗, 今井桂子

    日本オペレーションズ・リサーチ学会「都市のOR」ワークショップ2011  2011年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • po-leader を用いた MinMax 型 Clustered Boundary Labeling

    柿沼 亘, 今井桂子

    日本オペレーションズ・リサーチ学会「都市のOR」ワークショップ2011  2011年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Distance Trisector Curve に関する研究の誕生から発展までの経緯 招待

    浅野哲夫, 徳山豪, 今井桂子, 河村彰星

    電子情報通信学会コンピュテーション研究会  2011年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(招待・特別)  

    researchmap

  • 移動する点に対するラベル配置問題

    清家 陽佑, 今井 桂子

    地理情報システム学会第20回研究発表大会  2011年10月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 計算幾何学における離散幾何図形 招待

    今井桂子

    第10回情報科学技術フォーラム  2011年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(招待・特別)  

    researchmap

  • グラフにおける辺-辺隣接行列の完全ユニモジュラ性に対する必要十分条件

    松本雄介, 神山直之, 今井桂子

    情報処理学会アルゴリズム研究会  2011年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • A Simple Approximation Algorithm for Minimum Maximal Matching Problem 国際会議

    Yusuke Matsumoto, Naoyuki Kamiyama, Keiko Imai

    The 4th annual meeting of Asian association for algorithms and computation  2011年4月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • 対話型操作におけるメッシュ分割アルゴリズムの高速化

    今井良太, 今井桂子

    情報処理学会グラフィクスとCAD研究会  2011年2月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 制御点を用いたメッシュ変形手法

    工藤成司, 今井桂子

    情報処理学会グラフィクスとCAD研究会  2011年2月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Isophotic Metric を用いたペーパークラフトモデルの作製

    松本明展, 今井桂子

    情報処理学会アルゴリズム研究会  2011年1月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Open Surfaceメッシュに対するPolyCube Mapの構築

    佐藤晋, 今井桂子

    情報処理学会アルゴリズム研究会  2011年1月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 力学モデルを用いた引出し線ラベル配置の改良と応用

    相澤裕司, 今井桂子

    情報処理学会アルゴリズム研究会  2010年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 最小極大マッチング問題に対する (2-1/χ'(G)) 近似アルゴリズム

    松本 雄介, 神山 直之

    日本応用数理学会 2010年 研究部会 連合発表会  2010年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Web検索サービスにおける多義的なクエリの推薦手法

    今井良太, 戸田浩之, 関口祐一郎, 望月嵩由, 鈴木智也, 今井桂子

    第2回データ工学と情報マネジメントに関するフォーラム論文集  2010年2月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 階層型施設配置モデルを用いた集団下校経路の決定手法

    吉田祐太, 今井桂子

    「都市のOR」ワークショップ  2009年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 三角形メッシュに対する特徴線検出手法

    金寛宰, 今井桂子

    「都市のOR」ワークショップ  2009年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 引き出し線を用いた地図の外側へのラベル配置問題

    仁田亮, 今井桂子

    情報処理学会アルゴリズム研究会  2009年7月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 距離k分割線と一般図形のゾーン図の存在と一意性について

    今井桂子, 河村彰星, 村松悠, 徳山豪

    「理論計算機科学の深化と応用」研究集会  2009年2月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 鉄道路線を対象とした略地図の高速描画

    傳保 能幸, 今井桂子

    日本オペレーションズ・リサーチ学会「都市のOR」ワークショップ  2007年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 調和関数を用いたリメッシングのspectaclesによる改良

    長野真之, 今井桂子

    日本応用数理学会2007年度年会  2007年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Coincidence of Voronoi Diagrams in a Quantum State Space

    K. Kato, M. Oto, H. Imai, K. Imai

    Asian Conference on Quantum Information Science  2007年9月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • 全ラベル配置のための領域決定問題

    傳保能幸, 今井桂子

    情報処理学会アルゴリズム研究会  2007年5月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 地図上の経路探索におけるラベルの更新問題

    山本優二, 今井桂子

    情報処理学会アルゴリズム研究会  2007年5月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 調和関数を用いたリメッシングの改良

    長野真之, 今井桂子

    情報処理学会アルゴリズム研究会  2007年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • s-tパスのリスクに関する実験的考察

    松本雄介, 今井桂子

    情報処理学会アルゴリズム研究会  2006年7月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 多角形障害物のある領域における車両型ロボットの安全で滑らかな経路生成

    松本雄介, 鈴木一平, 今井桂子

    日本応用数理学会研究部会連合発表会  2006年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Guaranteed-Quality Anisotropic Mesh Generation for Domains with Curves

    Yusuke Yokosuka, Keiko Imai

    22nd European Workshop on Computational Geometry  2006年3月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • 高速描画のためのハーフエッジ階層を利用した視点および証明依存メッシュ簡略化

    宮村史朗, 今井桂子

    情報処理学会アルゴリズム研究会  2005年11月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 建物ポリゴンと道路リンクの幾何的不整合の解消法

    佐々木麗子, 今井桂子

    地理情報システム学会研究発表大会  2005年10月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Voronoi Diagrams for 1-qubit Pure Quantum States 国際会議

    Kimikazu Kato, Mayumi Oto, Hiroshi Imai, Keiko Imai

    The 2nd International Symposium on Voronoi Diagrams  2005年10月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • 障害物のある領域における車両型ロボットの安全な経路生成

    鈴木一平, 松本雄介, 今井桂子

    日本応用数理学会2005 年度年会  2005年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 曲線境界をもつ領域に対する品質保証つき非等方性メッシュ生成法

    横須賀 佑介, 今井 桂子

    日本応用数理学会2005 年度年会  2005年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 地図の拡大・縮小表示を念頭に置いたNLP問題に対するラベルサイズ最大化

    鳥海重喜, 今井桂子

    日本オペレーションズ・リサーチ学会 2005年秋季研究発表会  2005年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • パラメトリック曲面に対する品質保証付き非等方性メッシュ生成手法

    横須賀佑介, 今井桂子

    電子情報通信学会コンピュテーション研究会  2005年1月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 車両型ロボットの経路生成に関する一手法の提案

    鈴木一平, 今井桂子

    情報処理学会アルゴリズム研究会  2005年1月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 曲線境界をもつ領域に対する Ruppert のメッシュ生成法

    横須賀 佑介, 今井 桂子

    夏のLAシンポジウム  2005年 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 車両型ロボットに対する狭い道の通過可能性

    松本雄介, 今井桂子

    夏のLAシンポジウム  2005年 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • パラメトリック曲面に対する品質保証付きメッシュ生成手法

    横須賀佑介, 今井桂子

    日本応用数理学会年会  2004年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • CADデータへの応用を考慮したメッシュの圧縮

    宮村史朗, 今井桂子

    日本応用数理学会年会  2004年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Voronoi図を用いた長方形ロボットの経路探索

    鈴木一平, 今井桂子

    情報処理学会第66回全国大会  2004年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 三次元Delaunay三角形分割におけるランダム化点位置決定アルゴリズム

    小林陽介, 今井桂子

    情報処理学会第66回全国大会  2004年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 道案内図に対するラベル配置

    御厨健一, 今井桂子

    地理情報システム学会第7回空間ITワークショップ  2003年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 引出し線ラベル配置に対する解法と実装

    下原史義, 今井桂子

    情報処理学会アルゴリズム研究会  2003年11月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 地図における文字数を考慮したラベルサイズ最大化

    遠藤久雄, 今井桂子

    地理情報システム学会学術研究発表会  2003年10月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 2種類の施設を周遊する場合の商業利益分析

    海福長樹, 今井桂子

    日本応用数理学会2003年度年会  2003年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • アドホックネットワークにおけるプロードキャスト手法の実験的評価

    鄒良智, 今井桂子

    情報処理学会アルゴリズム研究会  2003年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 曲線データの圧縮に関するアルゴリズムと実験的評価

    安田祐一, 今井桂子

    情報処理学会アルゴリズム研究会  2003年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • プレッツェルリンクに対するJones多項式計算の効率化

    内海友雄, 今井桂子

    情報処理学会アルゴリズム研究会  2002年7月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 最小マンハッタンネットワーク問題に対する近似アルゴリズム

    加藤 亮, 今井 桂子, 浅野孝夫

    情報処理学会アルゴリズム研究会  2002年1月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 数値地図データへのラベルの自動配置に対する実験的評価

    亀田貴之, 今井 桂子

    地理情報システム学会 第2回空間ITワークショップ  2001年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • ラベル配置問題と地理情報処理への応用

    今井 桂子, 徳山 豪, 中野真一

    公開シンポジウム「アルゴリズム工学」  2001年10月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 引出し線を用いたラベル配置問題

    大塚善仁, 今井 桂子

    情報処理学会アルゴリズム研究会  2001年7月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 地図におけるラベル配置問題 ー 点と辺に対する解法の実験的評価

    今井 桂子, 亀田 貴之, 大塚善仁, 佐竹直也

    第7回``統合型地理情報システム''シンポジウム  2001年4月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 平面上における三角形分割を用いた点位置決定問題とその地図への応用

    工藤靖之, 今井桂子

    情報処理学会第62回(平成13年前期)全国大会  2001年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 点と辺に対するラベル配置問題

    亀田貴之, 大塚善仁, 佐竹直也, 今井桂子

    特定領域研究(B)「アルゴリズム工学」平成12年度成果報告  2001年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • ラベル配置問題に対する実験的評価

    亀田貴之, 今井桂子

    情報処理学会アルゴリズム研究会  2001年1月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • ラベル配置問題に対する貪欲法を用いた算法の実験的評価

    亀田貴之, 今井桂子

    地理情報システム学会第9回学術研究発表大会  2000年10月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 単体メッシュの数理的性質とその計算幾何学的知見

    今井桂子

    日本応用数理学会2000年度年会  2000年10月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • ラベル配置問題とその路線図への応用

    今井桂子, 亀田貴之

    第5回“統合型地理情報システム”シンポジウム  2000年4月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 絡み目のJones多項式計算の実際

    今井桂子, 今井浩, 関根京子

    電子情報通信学会コンピュテーション研究会  1999年5月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 単体メッシュの数理的性質と最近の計算幾何学的知見について 招待

    今井桂子

    日本応用数理学会メッシュ生成研究部会  1999年5月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(招待・特別)  

    researchmap

  • 地図内のラベル配置問題

    今井桂子, 中岡北巳, 林惠意

    第3回“統合型地理情報システム”シンポジウム  1999年4月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 3次元凸多面体上の近似最短経路アルゴリズムの実験的評価

    桜井裕邦, 今井桂子

    情報処理学会アルゴリズム研究会  1999年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • PAC学習モデルを用いた3次元空間における半空間の共通領域の学習

    岡田清孝, 今井桂子

    情報処理学会アルゴリズム研究会  1999年3月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 凸多角形の多角形領域内へのmaximin配置問題

    今井桂子

    地理情報システム学会第3回オブジェクト指向GISワークショップ  1999年1月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 正則単体メッシュの数理的性質とその計算量 招待

    今井桂子

    日本応用数理学会セミナー「メッシュ生成の数理」  1998年10月 

     詳細を見る

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

    researchmap

  • Voronoi Diagram by Divergences with Additive Weights 国際会議

    K. Sadakane, H. Imai, K. Onishi, M. Inaba, F. Takeuchi, K. Imai

    The Fourteenth Annual Symposium on Computational Geometry  1998年6月 

     詳細を見る

    記述言語:英語  

    researchmap

  • 幾何概念の学習に対する計算機実験による検証

    岡田清孝, 今井桂子

    Discrete and Computational Geometry Workshop  1997年11月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Parametric and Sensitivity Analysis of Network Reliability 国際会議

    H. Imai, K. Imai

    Reliability. Abstracts of the 5th International Conference on ``Parametric Optimization and Related Topics (PARAOPT V)''  1997年10月  PARAOPT Organizing Committee

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • ネットワーク信頼度計算の実際

    今村浩, 関根京子, 今井桂子

    日本オペレーションズ・リサーチ学会1997年度秋季研究発表会  1997年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • A package for Triangulations 国際会議

    T.Ono, Y.Kyoda, T.Masada, K.Hayase, T.Shibuya, M.Nakade, M.Inaba, H.Imai, K.Imai, D.Avis

    Proceedings of the 12th Annual Symposium on Computational Geometry, 5th Annual Video Review of Computational Geometry  1996年5月 

     詳細を見る

    記述言語:英語  

    researchmap

  • Enumeration of Regular Triangulations and Some Structures of Secondary Polytopes

    K.Imai, H.Imai

    情報処理学会アルゴリズム研究会  1996年1月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • 幾何的最適化問題とその周辺

    今井桂子

    電子情報通信学会情報・システムソサイエティ大会  1995年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 3角形分割と凸多面体

    今井浩, 今井桂子

    京都大学数理解析研究所短期共同研究「トーリック多様体の幾何と凸多面体」  1995年6月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 3角形分割とその周辺 招待

    今井桂子

    計算代数と計算幾何  1995年2月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 球面上の最適施設配置問題と動的Voronoi図

    今井桂子, 今井浩

    日本オペレーションズ・リサーチ学会平成6年度秋季研究発表会  1994年10月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Discrete Geometry and Dapvenport-Schinzel Sequence

    Keiko Imai

    京都大学数理解析研究所共同研究「計算幾何学と離散幾何学」  1994年5月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • Discrete Geometry and its Related Problems

    Keiko Imai

    The Fifth RAMP Symposium  1993年10月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(招待・特別)  

    researchmap

  • Graphical Degree Sequence Problems

    M.Takahashi, K.Imai, T.Asano

    情報処理学会アルゴリズム研究会  1993年5月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • On Weighted Dynamic Voronoi Diagrams

    K.Imai, H.Imai

    電子情報通信学会第6回回路とシステム軽井沢ワークショップ  1993年4月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • Generalized Geometric Fitting Problem and Weighted Dynamic Voronoi Diagrams

    K.Imai, H.Imai

    京都大学数理解析研究所研究集会「計算機構とアルゴリズム」  1993年2月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • Probing Hyperplanes by Lines

    青木保一, 今井浩, 今井桂子

    京都大学数理解析研究所応用数学合同研究集会  1992年12月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • 円の動的Voronoi図とその応用

    今井桂子, 今井浩

    日本応用数理学会平成4年度年会研究発表  1992年10月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 重みつき・高次の動的Voronoi図について

    今井桂子, 今井浩

    情報処理学会アルゴリズム研究会  1992年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 高次の動的Voronoi図とその応用

    今井桂子, 今井浩

    京都大学数理解析研究所研究集会「理論計算機科学とその周辺」  1992年1月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 超平面/曲面のアレンジメントの組合せ論的性質

    青木保一, 今井浩, 今井桂子

    京都大学数理解析研究所研究集会「数理モデルの解析における組合せ論的様相」  1991年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 3次元空間内の曲面のアレンジメントに関して

    今井桂子, 今井浩

    情報処理学会アルゴリズム研究会  1991年5月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 1つの変数に関して低次の交線をもつ代数曲面のアレンジメントについて

    今井桂子, 今井浩

    京都大学数理解析研究所研究集会「計算および計算量理論とその周辺」  1991年1月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Euclid距離による凸多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図

    今井浩, 今井桂子, 徳山豪

    情報処理学会第37回全国大会  1990年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Euclid距離による多角形配置問題とそれに関連する動的Voronoi図について

    今井桂子, 徳山豪

    情報処理学会アルゴリズム研究会  1990年5月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 凸多角形の多角形領域内へのmaximin配置問題とそれに関連した動的Voronoi図

    青沼裕美, 今井浩, 今井桂子, 徳山豪

    京都大学数理解析研究所共同研究「アルゴリズムと計算量の理論」  1990年2月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Minimax problem of n convex functions

    K.Imai, H.Imai

    電子情報通信学会コンピュテーション研究会  1989年9月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • 多次元Davenport-Schinzel列計算における線形化手法とその応用

    今井桂子

    情報処理学会アルゴリズム研究会  1989年7月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 幾つかの最適化基準の下での2次元点集合のクラスタリング/ハッシング算法

    浅野哲夫, 今井浩, 今井桂子

    情報処理学会アルゴリズム研究会  1989年6月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 動的な点に対するVoronoi図について

    今井桂子

    京都大学数理解析研究所  1989年1月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 対応の与えられた点集合間のミニマックス近似問題について

    今井桂子

    情報処理学会アルゴリズム研究会  1988年11月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 対応の与えられた点集合間のミニマックス近似問題について

    今井桂子, 今井浩

    情報処理学会第37回全国大会  1988年9月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • Algorithms for orthogonal L1 linear approximation of points in two and higher dimensions 国際会議

    H.Imai, K.Imai, P.Yamamoto

    The 13th International Symposium on Mathematical Programming  1988年8月  MPS

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • On orthogonal linear L_1 approximation of points

    P.Yamamoto, K.Imai, H.Imai

    京都大学数理解析研究所研究集会「計算アルゴリズムと計算量の基礎理論」  1988年2月 

     詳細を見る

    記述言語:英語   会議種別:口頭発表(一般)  

    researchmap

  • 線形作用素Φ^*:q(x)↦1/2α ∫_((1-α)x-α)^((1-α)x+α)q(ξ)dξの漸近的性質について

    森口繁一, 伊理正夫, 今井(蒲谷)桂子

    応京都大学数理解析研究所用数学合同研究集会  1987年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 円周上、球面上でのミニマックス型施設配置問題の計算複雑度について

    今井浩, 炭野重雄, 今井桂子

    電子情報通信学会コンピュテーション研究会  1987年11月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • ある病的な関数族に関連する作用素の性質の解析とその応用について

    蒲谷桂子, 伊理正夫

    京都大学数理解析研究所応用数学合同研究集会  1986年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

  • 一様分布に従う独立な確率変数の加重和に関連して現われる非解析的関数について

    蒲谷桂子, 伊理正夫

    京都大学数理解析研究所応用数学合同研究集会  1985年12月 

     詳細を見る

    記述言語:日本語   会議種別:口頭発表(一般)  

    researchmap

▼全件表示

受賞

  • 日本応用数理学会フェロー

    2020年6月   日本応用数理学会  

  • 電子情報通信学会フェロー

    2015年9月   電子情報通信学会  

共同研究・競争的資金等の研究課題

  • 動的環境における計算幾何学及び計算位相幾何学における基盤形成

    研究課題/領域番号:20K11682  2020年4月 - 2025年3月

    日本学術振興会  科学研究費助成事業  基盤研究(C)  中央大学

    今井 桂子, 森口 昌樹, 今井 浩

      詳細を見る

    配分額:4160000円 ( 直接経費:3200000円 、 間接経費:960000円 )

    計算幾何学は幾何情報処理のアルゴリズムを開発し,それを計算量理論によって解析する分野であり,計算位相幾何学は幾何情報の持つ位相そのものを抽出することや位相幾何学的な不変量をコンピュータで計算するための手法を構築する分野として発展してきた.本研究では,動的環境における計算幾何学の問題を計算位相幾何学の問題として捉え直すことにより,これまで個別に対応してきた動的環境における計算幾何学の問題を統一的に扱えるようにすることを目指して研究を進めている.
    昨年度に行った動的環境における計算幾何学や計算位相幾何学の問題の整理を基に今年度の研究を進めてきた.大規模な位相構造を持つ東京の地下鉄の路線図の描画はこれまであまり有効な手法が提案されていなかった.しかし,駅名も同時に自動配置することが可能な描画手法を提案し,これをまとめた研究を論文として公表した.ラベル配置問題においては,島の集合である島群に対するラベル配置問題に対して,拡大縮小を念頭においたラベル配置問題の解法を多くの計算幾何学の基本概念を利用することにより開発した.この手法に対して国土地理院地図を用いて計算機実験を行い,その有効性を確認した.提案した手法は島群に対してだけではなく,非連結な領域に対するラベル配置を可能にするものである.また,領域の境界に曲線を持つメッシュの張り合わせはこれまで難しかったが,既存手法を拡張し,平面の領域だけではなく,曲線を境界にもつ曲面メッシュにおいても張り合わせ可能なメッシュ生成手法を提案し,口頭発表で公表した.他にも量子計算に関する研究も行い,口頭発表を行った.

    researchmap

  • 動的環境における計算幾何学と計算位相幾何アルゴリズムに関する研究

    2016年4月 - 2020年3月

    日本学術振興会  科学研究費補助金  基盤研究(C) 

      詳細を見る

    資金種別:競争的資金

    配分額:4030000円 ( 直接経費:3100000円 、 間接経費:930000円 )

    researchmap

  • 視覚の心理・数理モデリングと第5世代不可能立体

    2016年4月 - 2019年3月

    日本学術振興会  科学研究費補助金  基盤研究(A) 

    杉原厚吉

      詳細を見る

    資金種別:競争的資金

    researchmap

  • 動的環境において地理情報システムに現れる最適化問題に関する研究

    2012年4月 - 2015年3月

    日本学術振興会  科学研究費補助金  基盤研究(C) 

      詳細を見る

    資金種別:競争的資金

    配分額:4680000円 ( 直接経費:3600000円 、 間接経費:1080000円 )

    researchmap

  • アスベスト関連相談に関する保健師向けガイドラインの構築と評価

    研究課題/領域番号:19592610  2007年 - 2010年

    日本学術振興会  科学研究費助成事業  基盤研究(C)  聖路加看護大学

    長松 康子, 佐居 由美, 今井 桂子

      詳細を見る

    配分額:4290000円 ( 直接経費:3300000円 、 間接経費:990000円 )

    中皮腫患者が急増し、国民の石綿に対する不安が高まっていたが、保健師向けの石綿関連相談ガイドラインが無かった。そこで、保健師向けの石綿関連相談ガイドラインの構築を目的として研究を開始した。まず、石綿関連NPOの石綿関連相談記録344件の内容を分析したところ、子どもを含む曝露不安、職業などからすでに曝露した人からの発症不安、関連疾患を発症した患者からの相談及び遺族からの相談に分類できた。相談内容に対して回答を行うには、医療のみならず、建築、法律、心理などの専門的知識が必要と考えられた。とくに、学校や工事現場などの環境曝露への不安に関する相談が多かったことから、子どもと保護者向けの石綿情報サイトを開設した。さらに全国の保健所の石綿関連相談事業についての調査を行った結果、前年度の相談件数は、平均5.3件で、担当者数は平均3.0人で看護師を配する保健所が7割を超えた。担当者で研修を受けたものは14%のみで、マニュアルを全く使用しない者が35.4%に上った。相談担当者の7割以上が該当業務について自信が無いと回答した。その理由として多かったのは、相談件数が減って知識が蓄積されない、相談内容が多岐にわたるなどであった。保健所の石綿関連健康相談担当者の自信度が低く、マニュアルがあまり使用されていないことから担当者のニーズにあったガイドライン作成が必要と考えられた。しかし、研究途中で他の研究者によって優れたガイドラインが開発されたので、保健所職員がもっとも相談対応が困難であると回答した患者の不安について研究目的を変更した。胸膜中皮腫患者14名を対象にインタビュー調査を行ったところ、患者は様々な困難を体験していた。困難は、進行の速い難知性疾患であること、希少疾患であること、石綿被害によって起こることという、中皮腫の特性に起因していた。このような複雑な困難が、次々と起こり、病気の進行が速いため、一つの困難が解決する前に新たな困難が発生して、困難の重層化が起こっていた。また、患者は医療従事者が経験と知識が不足しており、十分なケアを受けていないと感じていた。

    researchmap

  • 地理情報システムにおける研究用データ整備に関する研究

    2004年4月 - 2007年3月

    文部科学省  科学研究費補助金  基盤研究B 

      詳細を見る

    資金種別:競争的資金

    配分額:3300000円

    researchmap

  • ネットワーク上での社会的効用と個人的効用の対立問題に対するアルゴリズム的研究

    研究課題/領域番号:16092224  2004年 - 2007年

    日本学術振興会  科学研究費助成事業  特定領域研究  中央大学

    浅野 孝夫, 渡邉 敏正, 今井 桂子

      詳細を見る

    配分額:12200000円 ( 直接経費:12200000円 )

    ネットワーク上での対立問題をアルゴリズムの観点から研究し、計算困難性・近似困難性のより良い下界と上界を得ることが本研究の目的である。このような対立問題は、NP-困難な組合せ最適化問題であり、整数計画問題として定式化できるものが多い。したがって、近似アルゴリズムの理論が強力な道具である。
    以上を踏まえて、以下の研究計画に基づいて研究を実行した。
    1.社会的効用の最適化と利己的な各利用者の納得できる個人的効用の達成という対立問題の生じる実際の具体例とこれまでの研究を調査し、分類・整理・検討した。さらに、ゲーム理論や社会学、経済学で扱われている全体と個の対立問題のNash均衡に基づく理論的研究を調査し、分類・整理・検討した。
    2.本研究には近似アルゴリズムの設計と解析の技法が有効であることが既に知られている。そこで、上記の調査においては、高性能近似アルゴリズムの分野で最先端の研究をしている内外の研究者と情報およびアイデアを交換した。
    3.1,2の研究調査で得られた対立問題に対して、近似アルゴリズム、グラフ理論、計算幾何学の観点から研究し、近似アルゴリズムの設計と解析の技法の有効性を検討し分類整理した。さらに、計算困難性、近似困難性のより良い下界と上界を提案した。また、得られた上界(提案したアルゴリズム)に対して、その有効性を大規模な実物データで計算機実験を通して実証した。そして、得られた成果を内外の学会・論文誌で発表した。

    researchmap

  • 地理情報システムにおけるラベル配置問題に関する研究

    2001年4月 - 2004年3月

    日本学術振興会  科学研究費補助金  基盤研究C2 

      詳細を見る

    資金種別:競争的資金

    配分額:2500000円

    researchmap

  • 情報幾何モデルの離散構造解析に基づく高次幾何アルゴリズムとその応用の研究

    研究課題/領域番号:13480079  2001年 - 2004年

    日本学術振興会  科学研究費助成事業  基盤研究(B)  東京大学

    今井 浩, 森山 園子, 稲葉 真理, 今井 桂子, 兼定 邦彦, 淺井 健一, 丹羽 純平

      詳細を見る

    配分額:14800000円 ( 直接経費:14800000円 )

    本研究では,Web構造・量子情報構造や知識などコンピュータ内で対象を表現した際,対象物が自然と数値化されて本来の構造を反映した幾何空間が導入され,その位相幾何空間上での様々な情報処理アルゴリズムを研究・開発することを目指した.特に,その離散的構造を解析することによって,コンピュータで対象からの知識獲得など種々の高次の処理をその幾何構造を通して行うことを目的とする.本研究により,Web構造により構成される位相構造上でのアルゴリズムの開発,幾何構造を量子情報幾何の空間にまで広げて量子情報処理における幾何構造活用への発展、位相幾何構造としてシェリングとその双対構造の研究、さらにその計算代数への展開も図ることが実現できた.
    Web構造については,リンクによるページ間の頂戴規模グラフ構造の圧縮をその特性を活用して実現し,将来圧縮した情報上での検索の可能性も示すことができた.低次元位相幾何構造の代表的なものである単体的複体でのシェリングについて,それを有向マトロイドに拡張して計算代数的側面からも研究を展開する基礎成果を得た.
    量子情報処理においては,そのパワーの源である量子エンタングルメントについて,幾何構造を活用してエンタングルしている度合いにより構成される量子状態の階層構造を解明した.特に,量子エンタングルメント量と量子通信路容量の典型であるHolevo容量との関係が明らかになり,Holevo容量計算のための計算幾何アルゴリズムについて,量子情報幾何空間での計算幾何として独自の新展開を与えることができた.

    researchmap

  • 離散計算幾何学に関する共同研究

    1999年4月 - 2001年3月

    文部省  科学研究費補助金  基盤研究B2 

      詳細を見る

    資金種別:競争的資金

    配分額:3400000円

    researchmap

  • 動的および実時間環境における幾何構造の変化に関する統一的手法に関する研究

    1998年4月 - 2001年3月

    文部省  科学研究費補助金  特定領域研究B2 

      詳細を見る

    資金種別:競争的資金

    配分額:10200000円

    researchmap

  • 地理情報システムにおける計算幾何による品質保証高次処理の実現

    研究課題/領域番号:09558029  1997年 - 2000年

    日本学術振興会  科学研究費助成事業  基盤研究(B)  東京大学

    今井 浩, 今井 桂子, 稲葉 真理, 浅井 健一, 徳山 豪, 久保田 光一

      詳細を見る

    配分額:12800000円 ( 直接経費:12800000円 )

    本研究では,地理情報システムGISさらには高度交通システムITSの情報基盤としての整備・高次利用の強い要請に鑑み,GISでの情報処理に必須の高速幾何アルゴリズムの開発と,それに基づく地理情報システム全体の頑健性や品質を保証した計算に関する研究,さらにはそれらを標準化活動にまで昇華することを目指した.幾何アルゴリズムについては,地理情報空間におけるクラスタリングに多くの成果をあげ,情報幾何モデルも包含したGISデータの解析手法を提示した.また,地図でのラベリング問題,マッチング問題についても成果をあげた.
    具体的に,計算幾何において開発されている数値誤差に対して頑健なアルゴリズムをもとに,それらを用いて実現できるGISでの問題に取り組んだ.具体的には,街区データからの道路中心線自動抽出アルゴリズムを構築してその頑健性を実際の計算実験を通して示した.また,地図ラベル配置問題にも取り組み,実際の地下鉄網などを対象に,地図における様々な用件を満たす自動ラベル配置アルゴリズムについて研究を進め,システムを開発した.GISの大きな応用分野である高度交通システムITSについては,カーナビなど利用者の高度な質問に対応するためのアルゴリズム,具体的には利用者にとって意味ある選択のできる迂回路計算アルゴリズムを開発した.さらに,将来のさらなる高度化を支えるために必要な交通情報の自動獲得を目指して,土台となる交通時間計測システムについて研究を行った.商圏など近接関係を表す代表的構造であるVoronoi図については,その統計パラメタ空間への拡張を行ない,そこでの幾何構造がEuclid空間の場合と基本的に同じであることを示した.GISでは,単に幾何構造だけでなく,統計データなどもGISデータとして与えられるので,この手法を用いて幾何近接関係と様々な統計解析とを融合した地理データマイニングが可能となる.

    researchmap

  • モバイルコミュニケーション空間の空間データ化に関する共同研究

    1998年4月 - 1999年3月

    公的機関からの助成金(私大助成等) 

      詳細を見る

    資金種別:競争的資金

    配分額:3500000円

    researchmap

  • 離散計算幾何学に関する共同研究

    1998年4月 - 1999年3月

    文部省  科学研究費補助金  国際学術研究 

      詳細を見る

    資金種別:競争的資金

    配分額:2200000円

    researchmap

  • 動的環境における幾何情報を含んだ離散構造のためのアルゴリズムに関する研究

    1996年4月 - 1998年3月

    文部省  科学研究費補助金  基盤研究C2 

      詳細を見る

    資金種別:競争的資金

    配分額:2000000円

    researchmap

  • 離散・連続アプローチを融合した高度最適化システムの開発

    研究課題/領域番号:07555615  1995年 - 1996年

    日本学術振興会  科学研究費助成事業  基盤研究(B)  東京大学

    今井 浩, 村松 正和, 土谷 隆, 今井 桂子, 室田 一雄, 浅野 孝夫

      詳細を見る

    配分額:1900000円 ( 直接経費:1900000円 )

    コンピュータによる最適化技法は,その適用範囲が広いことから,新手法の開発・発見は,非常に大きなインパクトを色々な分野に対して与える.本研究では,これまでに各分担者が独自に開発した線形計画法に対する内点法・計算幾何算法・マトロイド理論・論理関数理論を用いたシステム解析技法について,融合した共同研究を本研究を通して遂行することにより,新たな理論的成果を上げるとともに,そのソフトウェアシステムを開発することを目的とした.
    本研究により,連続的な側面では線形計画の枠組を拡張した半正定値計画問題での内点法の拡張を行ない,離散的最適化の枠組からは離散凸理論の確立を果たした.これにより,線形計画問題と凸多面体を通して理解されていた連続構造と離散構造の橋渡しが,マトロイドや劣モジュラシステムなどをさらに拡張した枠組で可能になり,両方のアルゴリズム成果の融合が可能になった.この連続・離散の橋渡しを土台に,確率的手法を通した離散・連続アプローチの融合が実現した.具体的には,半正定値計画を論理式最大充足化問題に適用し,半正定値計画のレベルで連続値解を得た後,ランダム丸めすることにより離散解でよい近似解を構成し,詳細な解析を通して従来法を上回る近似性能の保証を可能にした.離散・連続の両面をもった幾何的最適化問題として辺長和最小3角形分割問題に取り組み,分枝切除法という連続性を活用した離散最適化のアプローチの有効性を実証した.離散システムの最も基本としての集合族を表現するモデルとして,論理関数処理法として注目されている2分決定グラフの理論を拡張し,集合族処理に適したアルゴリズムを開発するとともに,実際にシステムを開発して,その成果を広く公開している.

    researchmap

  • 動的環境における最適化問題の幾何手法によるアルゴリズムの研究開発

    1994年4月 - 1995年3月

    文部省  科学研究費補助金  奨励研究A 

      詳細を見る

    資金種別:競争的資金

    配分額:900000円

    researchmap

  • 計算幾何学アルゴリズムに関する共同研究

    研究課題/領域番号:06044058  1994年 - 1995年

    日本学術振興会  科学研究費助成事業  国際学術研究  東京大学

    今井 浩, 浅井 健一, 岩田 覚, 土谷 隆, 稲垣 宏, 今井 桂子, 浅野 孝夫, 杉原 厚吉, EDELSBRUNNER エルベルト, RAPPAPORT Da, TOUSSAINT Go, AVIS David, HELBERT Edel, DAVID Rappap, GODFRIED Tou, DAVID Avis

      詳細を見る

    配分額:6400000円 ( 直接経費:6400000円 )

    本科学研究費により平成6,7年度に渡って実施した国際共同研究について,その成果を報告する.この研究の中心テーマである計算幾何学は,幾何構造を有する図形などの情報処理問題を高速に解くアルゴリズムを,情報科学・情報工学でのアルゴリズム設計の立場から統一的に研究する分野である。これまでに,平面図形・空間図形に関係する問題を中心に,既存手法では解けなかったような大規模な問題を実用的時間内で解いたり,新たに生じてきた問題に対する新アルゴリスムを提供したりなどの有用な成果を上げてきた.本研究グループは,ここ十数年に渡って個々の研究者がそれぞれの国を訪問し,数カ月滞在するなどして共同研究を行ない,かなりの成果を上げてきた.しかし,個々の研究者での交流が主であり,グループ全体での研究会などの開催などは,国際会議などの前後の極く短期間の研究集会だけであり,個々の研究レベルの高さを,国際的な共同研究環境整備ができておらず,生かしきれていなかった面があった.それを本研究により,統合されたことによる成果を上げ,融合による新展開を図ることができた.
    具体的には,本科学研究では,グループの各分担者の研究成果が,普遍的な基礎分野での成果から応用に直結した大規模プログラムまで広範囲に渡ることに基づき,それらを融合させて,計算幾何学のみならず情報科学・工学の基礎理論での新展開を図ることを目標に国際共同研究を行なった.具体的成果としては,計算幾何ワークベンチ,特に3角形分割などの基本的幾何構造に関するパッケージ開発ができ,理論的にも本科学研究費の共同研究により一定期間に渡っての共同討議を行ない,今後に続く研究成果が得られた.具体的成果については,論文リストを参照されたい.特に,3角形分割のパッケージは,関連分野に関する北米で最も大きな会議のACM計算幾何会議において,論文発表を2件と,さらにビデオによるデモンストレーションを行なう予定である.このプロジェクトの大元は,カナダ側代表のAvis教授による逆探索と呼ばれるアイデアで,これを本科学研究を通じて日本側の最適化技法と融合させ,新展開を図ることができた.頑健な幾何計算などでも当初の目標通りの成果を上げることができた.また、本共同研究により,日本とカナダ・アメリカの研究交流を通じて,情報科学・情報工学の分野における日本での研究の特徴を生かした貢献を示せた.
    さらに,本共同研究を通して,D.Avis,D.Rappaport,H.Edelsbrunner教授との東京での共同研究が実現し,また日本側からは研究分担者として初年度に稲垣宏講師,岩田覚助手,また研究協力者の稲葉真理,小野剛氏が,さらに最終年度では浅野孝夫教授,浅井健一助手の北米訪問が実現され,McGill大学を中心に共同研究・討議を行なった.また,北米側のグループの来日については,共同研究の立場から海外旅費は全て向う持ちで,日本側からは一部の場合に国内滞在費を支出するにとどめた.さらに、カナダ側のグループの共同研究者であるJ.M.Robert,H.Everett副教授,さらにはH.Edelsbrunner教授が短期滞在した経験のあるアジア香港からS.-W.Cheng,M.Golin副教授らの来日へと交流が発展し,計算幾何のテーマに絞った共同研究会を開催することもできた.このように,本研究ではグループ内での大きな成果を着実に上げることはもとより,より広くアジア・環太平洋地域の研究者まで含めた交流を可能にし,国際研究協力の実を上げた.本研究の成果は既に日本語の教科書としても発表され,また開発されたパッケージについては,まずは国際会議で発表の後,インターネットなどを通じて,広く公開していく予定である.

    researchmap

  • 動的および実時間環境での離散的最適化問題とその連続体モデルに基づく解法の研究

    研究課題/領域番号:05452122  1993年 - 1995年

    日本学術振興会  科学研究費助成事業  一般研究(B)  東京大学

    今井 浩, 今井 桂子

      詳細を見る

    配分額:6400000円 ( 直接経費:6400000円 )

    本研究の目的は,離散構造内での構造がどんどん変化する動的な問題や,将来のことがわからない状況で実時間(オンライン)的に最適化の要求を解いていく問題といった新しいタイプの離散的最適化問題を中心に,それに対する種々の新技法の開発と,連続体モデル,特に確率的取扱に関する解法を研究することである.具体的には,刻一刻と変わる交通状況の下での最短路問題,移動体施設が動くときの施設配置問題,並列・分散環境での計算機資源に関するスケジューリング問題などに関して,従来の静的な環境や,将来の要求が全てわかっているオフライン環境とは違うアプローチについて、問題の定式化を含めて取り組んだ.
    動的最短路問題については,さらなる高速化が可能であることを示すことができた.これは,以前に解いた情報を採用して,過去の解を小規模修正する程度で変化した状況での最適解が効率よく求められることを示した.これにより,より精密な動的交通流解析などを実用的時間内に行なうことができる.オンライン環境でのアルゴリズムについては,分散システムでの情報共有の問題について,問題の定式化から検討し,そこから詳細な検討を加えることによって,より実現的な解析が行えることをを示し,重要な成果を得た.また,そこでは連続体モデルとの関係のランダム化というランダムな振舞をアルゴリズムの中に導入する技法について,それがオンラインアルゴリズムの開発でも有用であることを示した.動的幾何問題については,動的Voronoi図という概念の提唱と,その解析,構築アルゴリズムの開発を中心に研究し,関連して離散的クラスタリング問題と連続的クラスタリング問題の間の対応を利用したランダム化アルゴリズムの開発も行ない,種々の問題の普遍的構造を明らかにするとともに,アルゴリズムの面からも新しい展開を示した.

    researchmap

  • 非線形幾何手法による幾何的最適化問題におけるアルゴリズムの研究開発

    1993年4月 - 1994年3月

    文部省  科学研究費補助金  奨励研究A 

      詳細を見る

    資金種別:競争的資金

    配分額:800000円

    researchmap

  • 確率的挙動を示す学習アルゴリズムとそれによる学習概念のクラス分け

    研究課題/領域番号:05213201  1993年    

    日本学術振興会  科学研究費助成事業  重点領域研究  東京大学

    今井 浩, 今井 桂子

      詳細を見る

    配分額:1700000円 ( 直接経費:1700000円 )

    本年度の研究では,最終年度でもあるため研究課題のテーマ全般についてまとめることも行ないながら研究を行ない,以下の成果を上げた.
    (1)確率的挙動を示す学習アルゴリズムについて,特にkラベル空間を学習する問題について研究し,そのための基礎的な解析手法をまとめた.これにより,概念が最初からk種ある場合の学習に必要な例の数について,タイトな限界を与えることができた.これは,従来の正負2種ラベルを組み合わせてk(>2)種を表現するのより直接的でより改善された限界を与える.また,学習の複雑度の尺度としてkラベル空間の主細分関数を定義し,その重要性を指摘した.
    (2)関連した確率的学習でよく用いられる最近点探索の手法に関連したkボロノイ空間の複雑度を調べ,このような対象空間を確率的に学習する際の主細分関数を評価した.具体的には,分散に基づいたkクラスタリング問題に対して,初めてこれを学習するのに必要な例の数がkに関して線形であることを示した.さらに,その応用としてクラスタリングにおける学習問題に対して効率的な確率的挙動を示すアルゴリズムを与えた.
    (3)確率的な学習アルゴリズムでは,どうしても近似学習になる点に着目し,幾何概念の学習の際に付加情報がある場合を考え,それが幾何概念の質問による正確な学習につながる問題,付加情報が十分でない場合は近似的に学習する問題を考えた.これらは,3層のネットワーク関数において,各素子の関数として線形関数,乗算関数,最大値(あるいさ最小値)関数,しきい値関数を組み合わせたものが幾何概念に対応し,その幾何構造を用いることにより得られるものである.具体的には,ニューロコンピューティングに関係した幾何概念の内,凸多面体の学習,超平面集合の質問による正確な学習,超平面集合による空間の分割の近似的学習が可能であることを示した.

    researchmap

  • 確率的挙動を示す学習アルゴリズムとそれによる学習概念のクラス分け

    研究課題/領域番号:04229201  1992年    

    日本学術振興会  科学研究費助成事業  重点領域研究  東京大学

    今井 浩, 今井 桂子

      詳細を見る

    配分額:1900000円 ( 直接経費:1900000円 )

    本研究では,計算論的学習理論をもとに,より高度・柔軟な機械学習を実現することを目指している.特に,計算量的な観点から機械学習する対象として,普遍的な幾何構造をとりあげ,それに対する確率的な近似学習アルゴリズムと,質問を用いた正確な学習に取り組んでいる.本年度の研究では,昨年度の成果をさらに拡張し,対象kラベル空間の学習の難しさの尺度を導入し,kラベル空間の近似学習可能性に関する定理を与えた.またニューラルネットワークの基本構造である3層のネットワークにより表される関数の質問を用いた正確な学習について成果を上げた.以下,この2点について述べる.
    (kラベル空間の学習理論)従来の例からの学習の最も基本的な枠組では,正例・負例の2種の例しか考えなかった.しかし,それではk種類の分類がある場合の概念クラスに対しては不十分であった.概念が幾何的に解釈できる場合,正例・負例からの学習について,VC次元という尺度が知られている.これに対して,本研究ではこのkラベル空間の次元を新たに導入し,この次元を用いて,Voronoi空間の複雑度を定義し,その応用を示した.これは,学習対象のコンパクトな表現を与えることにより汎化を実現するものである.
    (3層ネットワーク関数の質問を用いた学習)3層ニューラルネットの最も基本的なモデルは,d個の入力,n素子の中間層・l素子の出力層の各素子を線形のしきい値関数としたものである.本年度のこれまでの研究で,各素子として,同様に基本的な入力の和・積・線形・最小値をとるものを考え,それらの組合せとして表される関数の正確な学習について調べ,これらの関数が多くの場合質問を用いて(O(n^d)とかO(dn)回とかの質問で)正確に学習可能であり,またしきい値関数の場合の近似学習の限界について示した.

    researchmap

  • 確率的挙動を示す学習アルゴリズムとそれによる学習概念のクラス分け

    研究課題/領域番号:03245201  1991年    

    日本学術振興会  科学研究費助成事業  重点領域研究  東京大学

    今井 浩, 今井 桂子, HOULE Michea

      詳細を見る

    配分額:2500000円 ( 直接経費:2500000円 )

    本年度の研究では、柔らかい学習を可能にする計算量に基づく学習理論のうち、確率的挙動を示す学習アルゴリズムについて、特にκラベル空間を学習する問題について研究し、またそのための基礎的な解析手法をまとめた。
    これまでの例からの学習の最も基本的な枠組では、ある概念クラスを学習したい時、その概念クラスに含まれる例(正例)とそれに含まれない例(負例)が与えられるとしていた。このような状況は、概念クラスが1つの場合に応対している。しかし、学習対象の概念クラスが1個だけでなく、κ個ある場合も一般に多い。そのような例としては、3層ニュ-ラルネットで各ユニットを線形のしきい値関数とみなしたときの、n入力層とm中間層で構成されるn次元空間の分割やk次元のk+1等分割問題などが上げられる。そのような場合も、概念クラスが1つの場合を階層的に組み合わせて対処できることもあるが、そうすると対処できたとしてもk個の概念クラスをまとめて取り扱った時よりなんらかの意味で悪くなることが予想される。
    そこで、k種のクラスがある場合をκラベル空間として定式化し、一般的なkラベル空間の複雑さに関する考察と、ランダムサンプリングによって学習する時の、ある指定された精度を高い確率で達成するために必要なサンプル数の評価を行ない、それを上述のk次元のk+1等分問題に適用した。その応用として、割り当てアルゴリズムの解析を行なった。これによって、正例と負例だけの基本的な場合を繰り返し組み合わせて複雑なものを表現するよりも、k種のものをまとめて取り扱うことにより、より効率的な処理が可能になることを示した。また、本研究はValiantのいわゆるPAC学習モデルでのVC次元を用いた学習理論について、その拡張を試みたものといえ、VC次元を拡張した容量的概念を、Chernoff限界などを用いて証明したものである。

    researchmap

▼全件表示

委員歴

  • 2011年10月 - 2023年9月

    日本学術会議   連携会員  

  • 2021年7月 - 2022年6月

    独立行政法人日本学術振興会   特別研究員等審査会委員  

  • 2018年8月 - 2018年10月

    独立行政法人 科学技術振興機構   未来社会創造事業 研究開発運営会議 外部専門家  

  • 2016年11月 - 2017年10月

    文部科学省   大学設置・学校法人審議会専門委員  

  • 2016年1月 - 2017年3月

    独立行政法人 大学評価・学位授与機構   国立大学教育研究評価委員会専門委員  

  • 2015年4月 - 2017年2月

    文部科学省   科学技術・学術審議会専門委員  

  • 2015年11月 - 2016年10月

    文部科学省   大学設置・学校法人審議会専門委員  

  • 2015年11月 - 2016年3月

    独立行政法人 科学技術振興機構   戦略的創造研究推進事業総括実施型研究事後評価委員  

  • 2014年12月 - 2015年11月

    独立行政法人 日本学術振興会   科学研究費委員会専門委員  

  • 2015年4月 - 2015年10月

    文部科学省   大学設置・学校法人審議会専門委員  

  • 2014年12月 - 2015年6月

    独立行政法人 科学技術振興機構   戦略的創造研究推進事業における追跡評価  

  • 2014年4月 - 2015年3月

    文部科学省   大学設置・学校法人審議会専門委員  

  • 2013年12月 - 2014年11月

    独立行政法人 日本学術振興会   科学研究費委員会専門委員  

  • 2013年11月 - 2014年3月

    独立行政法人 科学技術振興機構   戦略的創造研究推進事業総括実施型研究事後評価委員  

  • 2012年1月 - 2012年12月

    独立行政法人 日本学術振興会   科学研究費委員会審査第一部会総合領域小委員会委員  

  • 2009年1月 - 2009年12月

    独立行政法人 日本学術振興会   科学研究費委員会専門委員  

  • 2008年2月 - 2009年6月

    独立行政法人 大学評価・学位授与機構   国立大学教育研究評価委員会専門委員  

  • 2008年1月 - 2008年12月

    独立行政法人 日本学術振興会   科学研究費委員会専門委員  

  • 2005年1月 - 2005年12月

    独立行政法人 日本学術振興会   科学研究費委員会専門委員  

▼全件表示

社会貢献活動

  • 男女共同参画学協会連絡会運営委員会委員長

    2023年11月 - 2024年10月

     詳細を見る

  • 特定非営利活動法人 TECUM

    2019年5月 - 2023年5月

     詳細を見る

  • 学校法人津田塾大学評議員

    2015年7月 - 2019年7月

     詳細を見る

  • 特定非営利活動法人 女子中高生理工系キャリアパスプロジェクト

    2018年10月 -  

     詳細を見る