Journal of Computer Science and Technology ›› 2021, Vol. 36 ›› Issue (4): 910-921.doi: 10.1007/s11390-021-0095-8

Special Issue: Computer Graphics and Multimedia

• Regular Paper • Previous Articles     Next Articles

Method for Processing Graph Degeneracy in Dynamic Geometry Based on Domain Design

Hao Guan1,2,3, Yong-Sheng Rao1,*, Member, CCF, Jing-Zhong Zhang1, Sheng Cao4, Member, CCF, and Xiao-Lin Qin2,3, Member, CCF        

  1. 1 Institute of Computing Science and Technology, Guangzhou University, Guangzhou 510006, China;
    2 Chengdu Institute of Computer Applications, Chinese Academy of Sciences, Chengdu 610041, China;
    3 University of Chinese Academy of Sciences, Beijing 100049, China;
    4 School of Computer Science and Engineering, University of Electronic Science and Technology of China Chengdu 61173, China
  • Received:2019-10-10 Revised:2021-01-15 Online:2021-07-05 Published:2021-07-30
  • Contact: Yong-Sheng Rao
  • About author:Hao Guan is a postdoctor researcher in Institute of Computing Science and Technology, Guangzhou University, Guangzhou. He received his Ph.D. degree in computer science from University of Chinese Academy of Sciences, Beijing, in 2020. His research interests include computer graphics and educational software.
  • Supported by:
    This work is supported by the Sichuan Science and Technology Program of China under Grant Nos. 2018GZDZX0041 and 2020YFG0011, the National Natural Science Foundation of China under Grant No. 11701118, the Guangzhou Academician and Expert Workstation under Grant No. 20200115-9, and Key Disciplines of Guizhou Province of China—Computer Science and Technology under Grant No. ZDXK [2018]007.

A dynamic geometry system, as an important application in the field of geometric constraint solving, is widely used in elementary mathematics education; moreover, the dynamic geometry system is also a fundamental environment for automated theorem proving in geometry. In a geometric constraint solving process, a situation involving a critical point is often encountered, and geometric element degeneracy may occur at this point. Usually, the degeneracy situation must be substantively focused on during the learning and exploration process. However, many degeneracy situations cannot be completely presented even by the well-known dynamic geometry software. In this paper, the mechanisms causing the degeneracy of a geometric element are analyzed, and relevant definitions and formalized descriptions for the problem are provided according to the relevant modern Euclidean geometry theories. To solve the problem, the data structure is optimized, and a domain model design for the geometric element and the constraint relationships thereof in the dynamic geometry system are formed; furthermore, an update algorithm for the element is proposed based on the novel domain model. In addition, instances show that the proposed domain model and the update algorithm can effectively cope with the geometric element degeneracy situations in the geometric constraint solving process, thereby achieving unification of the dynamic geometry drawing and the geometric intuition of the user.

Key words: dynamic geometry; critical point; degeneracy; domain model;

[1] Gao X S, Jiang K. Survey on geometric constraint solving. Journal of Computer Aided Design & Computer Graphics, 2004, 16(4):385-396. DOI:10.3321/j.issn:1003-9775.2004.04.001. (in Chinese)
[2] Zhang J Z, Ge Q, Peng X C. Educational technology research should be in-depth discipline. e-Education Research, 2010, (2):8-13. DOI:10.13811/j.cnki.eer.2010.02.009. (in Chinese)
[3] Bokosmaty S, Mavilidi M F, Paas F. Making versus observing manipulations of geometric properties of triangles to learn geometry using dynamic geometry software. Computers & Education, 2017, 113:313-326. DOI:10.1016/j.compedu.2017.06.008.
[4] Ye Z, Cou S C, Gao X S. Visually dynamic presentation of proofs in plane geometry. Journal of Automated Reasoning, 2010, 45(3):213-241. DOI:10.1007/s10817-009-9162-5.
[5] Cou S C, Gao X S, Zhang J Z. Automated generation of readable proofs with geometric invariants. Journal of Automated Reasoning, 1996, 17(3):325-347. DOI:10.1007/BF00283133.
[6] Wu W T. Basic principles of mechanical theorem proving in elementary geometries. Journal of Automated Reasoning, 1986, 2(3):221-252. DOI:10.1007/BF02328447.
[7] Kapur D. Using Gröbner bases to reason about geometry problems. Journal of Symbolic Computation, 1986, 2(4):399-408. DOI:10.1016/S0747-7171(86)80007-4.
[8] Abánades M, Botana F, Kovács Z et al. Development of automatic reasoning tools in GeoGebra. ACM Communications in Computer Algebra, 2016, 50(3):85-88. DOI:10.1145/3015306.3015309.
[9] Rao Y S, Zhang J Z, Zou Y et al. An advanced operating environment for mathematics education resources. Science China (Information Sciences), 2018, 61(9):1-3. DOI:10.1007/s11432-017-9235-7.
[10] Muthanna T, Sivertsen E, Kliewer D et al. Coupling field observations and geographical information system (GIS)-based analysis for improved sustainable urban drainage systems (SUDS) performance. Sustainability, 2018, 10(12):Article No. 4683. DOI:10.3390/su10124683.
[11] Gillula J H, Hoffmann G M, Huang H et al. Applications of hybrid reachability analysis to robotic aerial vehicles. The International Journal of Robotics Research, 2011, 30(3):335-354. DOI:10.1177/0278364910387173.
[12] Kurniawati H, Du Y, Hsu D et al. Motion planning under uncertainty for robotic tasks with long time horizons. The International Journal of Robotics Research, 2011, 30(3):308-323. DOI:10.1177/0278364910386986.
[13] Chen H, Sheng W. Transformative CAD based industrial robot program generation. Robotics and ComputerIntegrated Manufacturing, 2011, 27(5):942-948. DOI:10.1016/j.rcim.2011.03.006.
[14] Deng W, Karaliopoulos M, Mühlbauer W et al. k-Fault tolerance of the Internet AS graph. Computer Networks, 2011, 55(10):2492-2503. DOI:10.1016/j.comnet.2011.04.009.
[15] Richter-Gebert J, Kortenkamp U H. Complexity issues in dynamic geometry. In Foundations of Computational Mathematics, Cucker F, Rojas J M (eds.), 2002, pp.355-404. DOI:10.1142/97898127780310015.
[16] Denner-Broser B. About tracing problems in dynamic geometry. Discrete & Computational Geometry, 2013, 49(2):221-246. DOI:10.1007/s00454-012-9473-x.
[17] Lin Q, Ren L, Chen Y et al. The design of intelligent dynamic geometric software based on the enhanced LIMD arithmetic. Chinese Journal of Computers, 2006, 29(12):2163-2171. (in Chinese)
[18] Hidalgo M R, Joan-Arinyo R. The reachability problem in constructive geometric constraint solving based dynamic geometry. Journal of Automated Reasoning, 2014, 52(1):99-122. DOI:10.1007/s10817-013-9280-y.
[19] Kortenkamp U H. Foundations of dynamic geometry[Ph.D. Thesis]. Swiss Federal Institute of Technology, 1999.
[20] Denner-Broser B. An algorithm for the tracing problem using interval analysis. In Proc. the 23rd ACM Symposium on Applied Computing, March 2008, pp.1832-1837. DOI:10.1145/1363686.1364127.
[21] Kortenkamp U H, Richter-Gebert J. A dynamic setup for elementary geometry. In Multimedia Tools for Communicating Mathematics, Borwein J, Morales M H, Rodrigues J F, Polthier K (eds.), Springer, 2002, pp.203-219. DOI:10.1007/978-3-642-56240-2_12.
[22] Su W, Wang P S, Cai C et al. A touch-operation-based dynamic geometry system:Design and implementation. In Proc. the 4th International Congress on Mathematical Software, August 2014, pp.235-239. DOI:10.1007/978-3-662-44199-237.
[23] Liu Z. Research of education-oriented key technologies on three-dimensional dynamic geometry[Ph.D. Thesis]. Central China Normal University, 2012. (in Chinese)
[24] Dubrovin B A, Fomenko A T, Novikov S P. Modern Geometry - Methods and Applications:Part Ⅱ:The Geometry and Topology of Manifolds. Springer Science & Business Media, 2012.
[25] Arango G. A brief introduction to domain analysis. In Proc. the 1994 ACM Symposium on Applied Computing, April 1994, pp.42-46. DOI:10.1145/326619.326656.
[26] Kang K C, Cohen S G, Hess J A et al. Feature-oriented domain analysis (FODA) feasibility study. Technical Report, Software Engineering Inst., Carnegie-Mellon Univ., PITTSBURGH, PA, 1990., Oct. 2020.
[27] Ajila S A, Tierney P J. The FOOM method-Modeling software product lines in industrial settings. In Proc. the 2002 International Conference on Software Engineering Research and Practice, June 2002.
[28] Chastek G, Donohoe P, Kang K C et al. Product line analysis:A practical introduction. Technical Report, Carnegie-Mellon Univ. Pittsburgh Pa Software Engineering Inst, 2001., Oct. 2020.
[29] Rao Y S, Guan H, Chen R X et al. A novel dynamic mathematics system based on the Internet. In Proc. the 2018 International Congress on Mathematical Software, July 2018, pp.389-396. DOI:10.1007/978-3-319-96418-8_46.
[30] Pan T. Using the inverse to prove the multi-circle problem. High-School Mathematics, 2008, 7:6-10. (in Chinese)
[1] Tian-Bi Jiang, Gui-Song Xia, Qi-Kai Lu, Wei-Ming Shen. Retrieving Aerial Scene Images with Learned Deep Image-Sketch Features [J]. , 2017, 32(4): 726-737.
[2] LU Ruqian (陆汝钤) and JIN Zhi (金芝). Formal Ontology: Foundation of Domain Knowledge Sharing and Reusing [J]. , 2002, 17(5): 0-0.
[3] LI Lian; WANG Jimin;. Fast Theorem-Proving and Wu s Method [J]. , 1999, 14(5): 481-486.
Full text



[1] Feng Yulin;. Recursive Implementation of VLSI Circuits[J]. , 1986, 1(2): 72 -82 .
[2] Liu Mingye; Hong Enyu;. Some Covering Problems and Their Solutions in Automatic Logic Synthesis Systems[J]. , 1986, 1(2): 83 -92 .
[3] Sun Zhongxiu; Shang Lujun;. DMODULA:A Distributed Programming Language[J]. , 1986, 1(2): 25 -31 .
[4] Huang Heyan;. A Parallel Implementation Model of HPARLOG[J]. , 1986, 1(4): 27 -38 .
[5] Min Yinghua;. Easy Test Generation PLAs[J]. , 1987, 2(1): 72 -80 .
[6] Sun Yongqiang; Lu Ruzhan; Huang Xiaorong;. Termination Preserving Problem in the Transformation of Applicative Programs[J]. , 1987, 2(3): 191 -201 .
[7] Qi Yulu;. A Systolic Approach for an Improvement of a Finite Field Multiplier[J]. , 1987, 2(4): 303 -309 .
[8] Feng Yulin;. Hierarchical Protocol Analysis by Temporal Logic[J]. , 1988, 3(1): 56 -69 .
[9] Bao Feng;. On the Condition for FSM Being a Scrambler[J]. , 1988, 3(1): 70 -74 .
[10] Chen Guoliang;. A Partitioning Selection Algorithm on Multiprocessors[J]. , 1988, 3(4): 241 -250 .

ISSN 1000-9000(Print)

CN 11-2296/TP

Editorial Board
Author Guidelines
Journal of Computer Science and Technology
Institute of Computing Technology, Chinese Academy of Sciences
P.O. Box 2704, Beijing 100190 P.R. China
  Copyright ©2015 JCST, All Rights Reserved