Discrete and computational geometry on the plane lattice

平面晶格上的离散和计算几何

• 批准号: 19500004
• 负责人: KANO Mikio
• 金额: $ 2.41万
• 依托单位: Ibaraki University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2007
• 资助国家: 日本
• 起止时间: 2007 至 2008
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-19500004/
• 关键词: 離散幾何; 計算幾何; 平面格子上の幾何; 赤点と青点の幾何; 平衡分割; 平面格子; 2種点集合; 多画像視覚分散; 幾何的マッチング; 図形の視覚分散; 赤点と青点; 2色点集合; 2等分割直角形; 準直角形

平面格子上の一般の位置に置かれた赤点と青点をそれぞれ2等分割する直角形が存在することを示し、同時にこのような2等分割直角形を求めるO(n log n)時間アルゴリズムを提案した。また、3つの凸領域で赤点と青点をそれぞれ3等分割できることも示した。さらに、格子線上に複数個の点の配置を許した場合にも、赤点と青点を同時に2等分割する準直角形の存在とその求め方など関連するいくつかの結果を得た。

The general position on the plane lattice is set to the red dot and the green dot, and the rectangular shape is divided into two equal parts. The time is O(n log n). The red dot and the green dot are divided into three equal parts. In addition, the arrangement of a plurality of points on the grid line may be divided into two equal parts, namely, the red point and the green point.

项目成果

General balanced subdivision of two sets of points in the plane

平面内两组点的一般平衡细分

• 发表时间: 2007
• 期刊: LNCS(Discrete Geometry, Combinatorics and Graph Theory) 4381
• 作者: Chuzo Iwamoto;Harumasa Yoneda;Kenichi Morita;and Katsunobu Imai;Tilakaratne WM;Mikio Kano
• 通讯作者: Mikio Kano

Invited Talk, Spanning trees with at most k leaves, International Conference on Graph Theory and it's Applications

特邀报告，Spanning trees with atmost k leaves，图论及其应用国际会议

• 发表时间: 2008
• 作者: Jayasooriya PR;Suraweera AK;Saku TT;Tilakaratne WM.;Chuzo Iwamoto;M.Kano
• 通讯作者: M.Kano

A Spanning tree with at most k leaves in a graph, 32nd Australasian Conference on Combinatorial Mathematics & Combinatorial Computing

图中最多有 k 个叶子的生成树，第 32 届澳大利亚组合数学会议

• 发表时间: 2007
• 作者: Katsunobu Imai;Yasuaki Masamori;Chuzo Iwamoto;and Kenichi Morita;M. Kano and Aung Kyaw
• 通讯作者: M. Kano and Aung Kyaw

木をアクセス構造にもつ多画像視覚型秘密分散法

具有树访问结构的多图像视觉秘密共享方法

• 发表时间: 2007
• 作者: 宇野美由紀;加納幹雄
• 通讯作者: 加納幹雄

Compatible Geometric Matchings Discrete and Computational Geometry

兼容的几何匹配离散和计算几何

• 发表时间: 2009
• 期刊: Vol.41
• 作者: B.M.Abrego;E.M.Arkin;S. Fernandez -Merchant;F. Hurtado;M. Kano;J.S.B. Mitchell;J. Urrutia
• 通讯作者: J. Urrutia