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

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

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 . 


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

  To appear in journal Theoretical Computer Science.  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.

  • 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 full version Here)

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

  • Fluctuated Fitting under the $\ell_1$-metric, (See 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

Maximal Parallelograms in a 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.
On the 1-factorizations of Middle Level Graph: Inner structure, Algorithm, and Application, (Arxiv Here)
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.,
                          Cipher                  in CTSC 2017,           
                          Daydayup            in CTSC 2016,           
                          Transitivity           in CCPC 2016,

                          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.