Development of Algorithms for Geometric Optimization and Data Analysis in Architecute

在过去的三年中，我们开发了几种用于建筑优化和数据分析的几何算法。所得结果总结如下。1)我们考虑了用n个斯坦纳点对球面上的凸多边形进行三角剖分的问题，使总边长比最小。这个问题出现在用三角形网格逼近圆顶结构曲面的应用中。建立了该问题与某一极值包装问题的关系。基于这种关系，我们开发了一个启发式产生6近似的球体（假设n选择足够大）。也就是说，生成的三角网格在这方面是均匀的。2)研究了将一个实值矩阵四舍五入为一个整值矩阵以最小化它们之间的n个l_p差测度的问题。为了定义l -p差异测度，我们引入矩阵的一组区域（刚性子矩阵），并考虑由该族定义的超图。首先利用具有凸分段线性目标函数的整数规划问题研究了舍入问题，并给出了l_p -差异的非平凡上界。我们提出了几个有趣的区域族，可以针对这些区域开发有效的算法。结果表明，该方法适用于开发高质量的数字半调软件。3)我们开发了一种基于数学规划和遗传算法的优化方法，用于在可能的非矩形场地中寻找房间，通道和门道的最佳地板布局。4)我们开发了一种新的方法，可以定量地阐明建筑内部空间照片上的印象与其彩色图像的物理特征之间的关系。通过问卷调查和实验验证了该方法的有效性。

Over the last three years, we have developed several geometric algorithms for optimization and data analysis in architecture. The summary of the results obtained as follows.1) We considered the problem of triangulating a convex polygon on spheres using n Steiner points that minimizes the overall edge length ratio. The problem arises in an application to approximation of curved surfaces of dome structures by triangular meshes. We establish a relation of this problem to a certain extreme packing problem. Based on this relationship, we develop a heuristic producing 6-approximation for spheres (provided n is chosen sufficiently large). That is, the produced triangular mesh is uniform in this respect.2) We studied the problem of rounding a real-valued matrix into an integer-valued matrix to minimize a n L_p-discrepancy measure between them. To define the L-p-discrepancy measure, we introduce a family of regions (rigid submatrices) of the matrix, and consider a hypergraph defined by the family. We first investigate the rounding problem by using integer programming problems with convex piecewise-linear objective functions, and give some nontrivial upper bounds for the L_p-discrepancy. We propose several interesting family of regions for which an efficient algorithm can be developed. We show that our approach is suitable for developing a high-quality digital-halftoning software.3) We developed an optimization method for finding an optimal floor layout of rooms, passages and door ways in a possibly non-rectangular site, based on mathematical programming as well as genetic algorithm.4) We developed a new method that quantitatively clarifies the relationship between the impression perceived on an photo of an architectural internal space and the phsical features of its color image. The effectiveness of the method was verified through questionnaires and experiments.