Kai Jin
Postdoc Fellow
Institute for Interdisciplinary Information Sciences

Address: Department of Computer Science, University of Hong Kong
Tel: +852 54064508 +86 13811623325 +852 28578273

Research Interests

    Geometry,    Algorithms,    Game Theory,   Combinatorics

Education and Experience

2018-now            Postdoc at Hong Kong University of Science and Technology
2016-2018          Postdoc at University of Hong Kong

2008-2016          Ph.D, Theoretical Computer Science, Tsinghua University.  Supervised by Andrew Yao.
2004-2008          Special Pilot CS Class (YAO class), B.S., Computer Science and Technology, Tsinghua University

Selected Honors

2002,2003         Gold medals in China National Olympiad in Informatics.
2005                   Champion of ACM/ICPC regional contest, Chengdu (as the team leader)
2006                   19-th place of ACM/ICPC word finals (as the team leader)

PhD. Thesis

When Convexity meets Parallelism – a New Geometric Structure and Its Application in Finding the Maximal Parallelograms in Convex Polygons,
supervised by Prof. Andrew Yao and advised by Prof Haitao Wang.

See http://arxiv.org/abs/1512.03897 . 


  • A Generalization of Self-Improving Algorithms (See Here)

Symposium on Computational Geometry, 2020. Coauthors: S.-W. Cheng, M.-K. Chiu, M.T. Wong. 

  • Near-Linear Time Approximation Schemes for Geometric Maximum Coverage(See Here)

Theoretical Computer Science  Volume 725, 16 May 2018. Coauthors: J. Li, H. Wang, B. Zhang, N. Zhang

  • On the Power of Dominated Players in Team Competitions, (See Here )

  the 15th conference in Autonomous agents and multiagent systems (AAMAS16). Coauthors: Pingzhong Tang, Shiteng Chen.

  • Cooperation via Codes in restricted Hat Guessing Games, (See Here)
      the 18th conference in Autonomous agents and multiagent systems (AAMAS19). Coauthors: Zhaoquan Gu, Ce Jin.
  • Extensions of Self-Improving Sorters, (See Here)
      Agorithmica 2020.  Coauthors: Siu-Wing Cheng, Lie Yan. 
  • On 1-factorizations of Bipartite Kneser Graphs  (See Here)
     The 25th International Computing and Combinatorics Conference (COCOON'19)

  • Computing the Pattern Waiting Time: A Revisit of the Intuitive Approach, (See Here)

  the 27th International Symposium on Algorithms and Computation (ISAAC16)

  • Finding the Maximum Area Parallelogram in a Convex Polygon (See Here),

  the 23rd Canadian Conference on Computational Geometry 2011 (CCCG11). Coauthor: Kevin Matulef

  • Optimal Partitioning Which Maximizes the Weighted Sum of Products, (See Here and full version Here)

  the 11th  International Frontiers of Algorithmics Workshop (FAW2017).

  • Fluctuated Fitting under the $\ell_1$-metric, (See Here and full version Here)

  the 11th  International Frontiers of Algorithmics Workshop (FAW2017).

  • Ascending Sequences with Neighboring Elements add up to Perfect Square Numbers  (See Here)

  Notes on Number Theory and Discrete Mathematics (NNTDM),Volume 23, 2017

Ongoing papers

A Geometric Structure Associated with the Convex Polygon,  (Arxiv Here)
Comment: A small world is created here. Strongly Recommanded!

Maximal Area Triangles in a Convex Polygon, (Arxiv Here)
Computing the Maximal Area Triangle in a convex polygon is a very classic problem in geometric optimization in CG. Surprisingly, the previous known linear-time algorithm by Dobkin and Snyder (see their FOCS paper Here) for this problem is incorrect! This is recently discoverd by Keikha, Löffler, Urhausen, and Hoog [here], where redesigning a linear-time algorithm has been proposed as an open problem. I resolved it in this paper by presenting a linear-time algorithm which is simple and delightful.

Finding all Maximal Area Parallelograms in a Convex Polygon,  (Arxiv Here)
This paper is the full version of my CCCG11 paper.
Among others, it presents an $O(n^2)$ time algorithm for finding Maximal Area Parallelogram.

Minimum Area All-flush Triangles Circumscribing a Convex Polygon (Arxiv Here)
Coauthor: Zhiyi Huang

Professional Experience

2010         TA, in the course on Theoretical computer science (instructed by Prof. Xiaoming Sun).
2012         Visiting scholar at University of Notre Dame
2015         TA, in the course on Algorithm Design (Instructed by Prof. Jian Li).

Other experiences

I serve as a student coach in China Olympiad Informatics team. I design creative problems for many Olympic competition of Information, e.g.,
                          Ingenious Latin, Fragments, Dead4gon,          in   ACM-HK-regional 2018,
                          Cipher                  in CTSC 2017,           
                          Daydayup            in CTSC 2016,           
                          Transitivity, Parallelogram           in CCPC 2016,

                          Dice                      in SCOI 2009,           
                          Polya’s Pocket      in NOI2006,
                          Shooting Game    in CTSC2006,            
                          Comb and etc.     in HNTSC 2005.


  • Listen to Music, Tennis, Swim.