Joint Research on Algorithms in Computational Geometry

日本教育、科学、体育和文化部联合研究国际科学研究方案的科学研究补助金已于1994和1995学年实施。该项目通过将日本，加拿大和美国的计算几何领域的活跃研究人员聚集在一起，以该小组每个成员的建立为基础，制定该领域的新课题。事实上，一些小组成员有机会在加拿大和日本进行短期合作，但由于时间和成员人数的限制，这种联合研究规模非常小。通过这个项目，我们组的所有研究人员可以聚集在一起讨论当今最活跃的话题，通过这个项目，我们已经发展了几何枚举，生成和计数的理论，基于我们的成员提出的技术。具体地说，反向搜索，二叉决策图和多面体的方法被证明是强大的工具，以解决大尺寸的几何问题，不能解决现有的方法。这是通过在该援助赠款的基础上在加拿大和日本多次交流想法而实现的。事实上，我们小组的国际合作已经扩展到亚太地区，吸引了这些地区的许多研究人员加入我们。从论文列表中可以看出，我们的成果已经发表。一个值得注意的出版物在日本是一本书的大卫阿维斯和Hiroshi今井计算几何。关于三角测量的编程包，技术演示和视频演示将在今年的第12届ACM计算几何研讨会上进行，这是该领域最大的活动之一。

This Grant-in Aid for Scientific Research in the International Scientific Research Program for Joint Research of the Ministry of Education, Science, Sports and Culture of Japan have been carried out for 1994 and 1995 academic years. This project was applied to the program by bringing making active researchers in computational geometry in Japan, Canada and US together to work out for new topics in the field based on the establishments of each member of this group. In fact, some of the group members had chances to work together in Canada and Japan for a short period, but such joint research was a very small-scale one due to the constraints about the time and the number of members. By this project, all the researchers in our group can gather together to discuss the most active topics nowadays.By this project, we have developed the theory of geometric enumeration, generation and counting based on the techniques proposed by our members. Specifically, reverse search, binary decision diagrams and polytopal approaches are demonstrated to be powerful tools to solve geometric problems of large size which could not be solved by the existing methods. This was achieved by exchanging ideas in Canada and Japan several times based on this Grant-in-Aid. In fact, the international cooperation between our group has been extended to Asian/Pacific Area by attracting many research in these areas to join us.Our results have been published as is seen from the list of papers. A notable publication in Japanese is a book by David Avis and Hiroshi Imai on Computational Geometry. About the programming package on triangulations, a technical presentation and a video presentation will be done at the 12th ACM Symposium on Computational Geometry this year, which is one of the biggest event in the field.