We use a variational principle to prove an existence and uniqueness theorem for planar weighted Delaunay triangulations (with non-intersecting site-circles) with prescribed combinatorial type and circle intersection angles. Such weighted Delaunay triangulations may be interpreted as images of hyperbolic polyhedra with one vertex on and the remaining vertices beyond the infinite boundary of hyperbolic space. Thus the main theorem states necessary and sufficient conditions for the existence and uniqueness of such polyhedra with prescribed combinatorial type and dihedral angles. More generally, we consider weighted Delaunay triangulations in piecewise flat surfaces, allowing cone singularities with prescribed cone angles in the vertices. The material presented here extends work by Rivin on Delaunay triangulations and ideal polyhedra.
For a comprehensive bibliography on circle packings and circle patterns we refer to Stephenson's monograph @cite_17 . Here, we can only attempt to briefly discuss some of the the most important and most closely related results.
@cite_17
2082107757 2752916745 2143075606 2141957180
Part I. An Overview of Circle Packing: 1. A circle packing menagerie 2. Circle packings in the wild Part II. Rigidity: Maximal Packings: 3. Preliminaries: topology, combinatorics, and geometry 4. Statement of the fundamental result 5. Bookkeeping and monodromy 6. Proof for combinatorial closed discs 7. Proof for combinatorial spheres 8. Proof for combinatorial open discs 9. Proof for combinatorial surfaces Part III. Flexibility: Analytic Functions: 10. The intuitive landscape 11. Discrete analytic functions 12. Construction tools 13. Discrete analytic functions on the disc 14. Discrete entire functions 15. Discrete rational functions 16. Discrete analytic functions on Riemann surfaces 17. Discrete conformal structure 18. Random walks on circle packings Part IV: 19. Thurston's Conjecture 20. Extending the Rodin Sullivan theorem 21. Approximation of analytic functions 22. Approximation of conformal structures 23. Applications Appendix A. Primer on classical complex analysis Appendix B. The ring lemma Appendix C. Doyle spirals Appendix D. The brooks parameter Appendix E. Schwarz and buckyballs Appendix F. Inversive distance packings Appendix G. Graph embedding Appendix H. Square grid packings Appendix I. Experimenting with circle packings. In this paper we consider the Online Bin Packing Problem in three variants: Circles in Squares, Circles in Isosceles Right Triangles, and Spheres in Cubes. The two first ones receive an online sequence of circles (items) of different radii while the third one receive an online sequence of spheres (items) of different radii, and they want to pack the items into the minimum number of unit squares, isosceles right triangles of leg length one, and unit cubes, respectively. For Online Circle Packing in Squares, we improve the previous best-known competitive ratio for the bounded space version, when at most a constant number of bins can be open at any given time, from 2.439 to 2.3536. For Online Circle Packing in Isosceles Right Triangles and Online Sphere Packing in Cubes we show bounded space algorithms of asymptotic competitive ratios 2.5490 and 3.5316, respectively, as well as lower bounds of 2.1193 and 2.7707 on the competitive ratio of any online bounded space algorithm for these two problems. We also considered the online unbounded space variant of these three problems which admits a small reorganization of the items inside the bin after their packing, and we present algorithms of competitive ratios 2.3105, 2.5094, and 3.5146 for Circles in Squares, Circles in Isosceles Right Triangles, and Spheres in Cubes, respectively. We show that the analogue of Hamilton’s Ricci flow in the combinatorial setting produces solutions which converge exponentially fast to Thurston’s circle packing on surfaces. As a consequence, a new proof of Thurston’s existence of circle packing theorem is obtained. As another consequence, Ricci flow suggests a new algorithm to find circle packings. Given a set @math of @math strings of total length @math , our task is to report the "most relevant"strings for a given query pattern @math . This involves somewhat more advanced query functionality than the usual pattern matching, as some notion of "most relevant" is involved. In information retrieval literature, this task is best achieved by using inverted indexes. However, inverted indexes work only for some predefined set of patterns. In the pattern matching community, the most popular pattern-matching data structures are suffix trees and suffix arrays. However, a typical suffix tree search involves going through all the occurrences of the pattern over the entire string collection, which might be a lot more than the required relevant documents. The first formal framework to study such kind of retrieval problems was given by [Muthukrishnan, 2002]. He considered two metrics for relevance: frequency and proximity. He took a threshold-based approach on these metrics and gave data structures taking @math words of space. We study this problem in a slightly different framework of reporting the top @math most relevant documents (in sorted order) under similar and more general relevance metrics. Our framework gives linear space data structure with optimal query times for arbitrary score functions. As a corollary, it improves the space utilization for the problems in [Muthukrishnan, 2002] while maintaining optimal query performance. We also develop compressed variants of these data structures for several specific relevance metrics.