풍선 비틀기로 다면체 만들기: 최소 풍선 수와 길이를 찾는 알고리즘

Computational Balloon Twisting: The Theory of Balloon Polyhedra [pdf]

이 논문은 풍선 동물과 풍선 다면체의 기하학적·알고리즘적 이론을 제시합니다. 풍선으로 만든 구조를 그래프로 모델링하고, 주어진 그래프를 정확히 만들기 위한 최소 풍선 수를 찾는 알고리즘을 제공합니다. 또한 풍선을 재사용하거나 지름길을 허용할 때 필요한 최소 총 길이를 계산하는 방법을 다룹니다. 반면, 동일한 길이의 풍선만으로 최적 구성을 만들 수 있는지 판별하는 문제는 NP-완전임을 증명합니다. 저자들은 이 연구가 교육과 건축 구조물(에어 빔) 설계에 응용될 수 있다고 설명합니다.