Thurston proposed that conformal mappings can be approximated by circle packing isomorphisms and the approach can be implemented efficiently. Based on the circle packing methods the rate of convergence of approximatin...Thurston proposed that conformal mappings can be approximated by circle packing isomorphisms and the approach can be implemented efficiently. Based on the circle packing methods the rate of convergence of approximating solutions for quasiconformal mappings in the plane is discussed.展开更多
Rodin and Sullivan （1987） proved Thurston＇s conjecture that a scheme based on the Circle Packing Theorem converges to the Riemann mapping, thereby proved a refreshing geometric view of the Riemann Mapping Theorem. ...Rodin and Sullivan （1987） proved Thurston＇s conjecture that a scheme based on the Circle Packing Theorem converges to the Riemann mapping, thereby proved a refreshing geometric view of the Riemann Mapping Theorem. Naturally, we consider to use the ellipses to pack the bounded simply connected domain and obtain similarly a sequence simplicial homeomorphism between the ellipse packing and the circle packing. In this paper, we prove that these simplicial homeomorphism approximate a quasiconformal mapping from the bounded simply connected domain onto the unit disk with the modulus of their complex dilatations tending to 1 almost everywhere in the domain when the ratio of the longer axis and shorter axis of the ellipse tending to ∞.展开更多
We introduce the character of Thurston's circle packings in the hyperbolic background geometry.Consequently, some quite simple criteria are obtained for the existence of hyperbolic circle packings. For example,if ...We introduce the character of Thurston's circle packings in the hyperbolic background geometry.Consequently, some quite simple criteria are obtained for the existence of hyperbolic circle packings. For example,if a closed surface X admits a circle packing with all the vertex degrees d_(i)≥7, then it admits a unique complete hyperbolic metric so that the triangulation graph of the circle packing is isotopic to a geometric decomposition of X. This criterion is sharp due to the fact that any closed hyperbolic surface admits no triangulations with all d_(i)≤6. As a corollary, we obtain a new proof of the uniformization theorem for closed surfaces with genus g≥2;moreover, any hyperbolic closed surface has a geometric decomposition. To obtain our results, we use Chow-Luo's combinatorial Ricci flow as a fundamental tool.展开更多
The problem of packing circles into a domain of prescribed topology is considered. The circles need not have equal radii. The Collins-Stephenson algorithm computes such a circle packing. This algorithm is parMlelized ...The problem of packing circles into a domain of prescribed topology is considered. The circles need not have equal radii. The Collins-Stephenson algorithm computes such a circle packing. This algorithm is parMlelized in two different ways and its performance is reported for a triangular, planar domain test case. The implementation uses the highly parallel graphics processing unit （GPU） on commodity hardware. The speedups so achieved are discussed based on a number of experiments.展开更多
With a NP hard problem given, we may find a equivalent physical world. The rule of the changing of the physical states is simply the algorithm for solving the original NP hard problem .It is the most natural algorithm...With a NP hard problem given, we may find a equivalent physical world. The rule of the changing of the physical states is simply the algorithm for solving the original NP hard problem .It is the most natural algorithm for solving NP hard problems. In this paper we deal with a famous example , the well known NP hard problem——Circles Packing. It shows that our algorithm is dramatically very efficient. We are inspired that, the concrete physics algorithm will always be very efficient for NP hard problem.展开更多
We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle...We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.展开更多
We give an example which shows that the Burago’s bounded distance theorem does not hold in a non-intrinsic metric case. The argument is based on the classical answer to the densest circle packing problem in ?2.
In this paper, we present a new proof of the uniqueness of Koebe-Andreev-Thurston theorem. Our method is based on the argument principle in complex analysis and reviews the connection between the circle packing theore...In this paper, we present a new proof of the uniqueness of Koebe-Andreev-Thurston theorem. Our method is based on the argument principle in complex analysis and reviews the connection between the circle packing theorem and complex analysis.展开更多
基金This project is supported in part by NSF of China(60575004, 10231040)NSF of GuangDong, Grants from the Ministry of Education of China(NCET-04-0791)Grants from Sun Yat-Sen University
文摘Thurston proposed that conformal mappings can be approximated by circle packing isomorphisms and the approach can be implemented efficiently. Based on the circle packing methods the rate of convergence of approximating solutions for quasiconformal mappings in the plane is discussed.
基金supported by the National Natural Science Foundation of China(10701084)Chongqing Natural Science Foundation (2008BB0151)
文摘Rodin and Sullivan （1987） proved Thurston＇s conjecture that a scheme based on the Circle Packing Theorem converges to the Riemann mapping, thereby proved a refreshing geometric view of the Riemann Mapping Theorem. Naturally, we consider to use the ellipses to pack the bounded simply connected domain and obtain similarly a sequence simplicial homeomorphism between the ellipse packing and the circle packing. In this paper, we prove that these simplicial homeomorphism approximate a quasiconformal mapping from the bounded simply connected domain onto the unit disk with the modulus of their complex dilatations tending to 1 almost everywhere in the domain when the ratio of the longer axis and shorter axis of the ellipse tending to ∞.
基金supported by National Natural Science Foundation of China (Grant Nos. 11871094 and 12122119)supported by National Natural Science Foundation of China (Grant No. 12171480)+1 种基金Hunan Provincial Natural Science Foundation of China (Grant Nos. 2020JJ4658 and 2022JJ10059)Scientific Research Program Funds of National University of Defense Technology (Grant No. 22-ZZCX-016)。
文摘We introduce the character of Thurston's circle packings in the hyperbolic background geometry.Consequently, some quite simple criteria are obtained for the existence of hyperbolic circle packings. For example,if a closed surface X admits a circle packing with all the vertex degrees d_(i)≥7, then it admits a unique complete hyperbolic metric so that the triangulation graph of the circle packing is isotopic to a geometric decomposition of X. This criterion is sharp due to the fact that any closed hyperbolic surface admits no triangulations with all d_(i)≤6. As a corollary, we obtain a new proof of the uniformization theorem for closed surfaces with genus g≥2;moreover, any hyperbolic closed surface has a geometric decomposition. To obtain our results, we use Chow-Luo's combinatorial Ricci flow as a fundamental tool.
基金Project supported by the Basic Science Research Program through the National Research Foundation of Korea (NRF) by the Ministry of Education, Science and Technology (No. 2012-0002715)NSF Grants CPATH (Nos. CCF-0722210 and CCF-0938999)+1 种基金DOE award (No. DE-FG52-06NA26290)a gift from the Intel Corporation
文摘The problem of packing circles into a domain of prescribed topology is considered. The circles need not have equal radii. The Collins-Stephenson algorithm computes such a circle packing. This algorithm is parMlelized in two different ways and its performance is reported for a triangular, planar domain test case. The implementation uses the highly parallel graphics processing unit （GPU） on commodity hardware. The speedups so achieved are discussed based on a number of experiments.
基金86 3National High-Tech Program of China(86 3-30 6 -0 5 -0 3-1) National Natural Science Foundation of China(193310 5 0 ) Chi
文摘With a NP hard problem given, we may find a equivalent physical world. The rule of the changing of the physical states is simply the algorithm for solving the original NP hard problem .It is the most natural algorithm for solving NP hard problems. In this paper we deal with a famous example , the well known NP hard problem——Circles Packing. It shows that our algorithm is dramatically very efficient. We are inspired that, the concrete physics algorithm will always be very efficient for NP hard problem.
基金This work is partially supported by Utah State University under Grant No.A13501.
文摘We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.
基金This work was partially supported by the Natural Science Foundation of Hunan Province(Grant No.06555009)Scientific Research Fund of Hunan Provincial Education Department(Grant No.00C194)
文摘We give an example which shows that the Burago’s bounded distance theorem does not hold in a non-intrinsic metric case. The argument is based on the classical answer to the densest circle packing problem in ?2.
基金Supported by National Natural Science Foundation of China (Grant No. 10701084)
文摘In this paper, we present a new proof of the uniqueness of Koebe-Andreev-Thurston theorem. Our method is based on the argument principle in complex analysis and reviews the connection between the circle packing theorem and complex analysis.
