Jaehoon Chung

Computational geometry · data structures · algorithms for AI

Jaehoon Chung

AI Fellow (AI Assistant Professor at KIAS) Center for AI and Natural Sciences

I work on computational geometry, data structures, and AI-assisted algorithm design, with a current focus on high-dimensional proximity search.

Email CV GitHub
Portrait of Jaehoon Chung

01 / Research

Research areas

Geometric and combinatorial algorithms with provable guarantees.

01

Computational geometry

Polygon partitioning, covering, containment, and approximation; lower bounds in geometric optimization.

02

Algorithmic primitives for AI

Distribution-aware nearest-neighbor search, weighted selection, and geometric optimal transport.

03

AI-assisted algorithm design

Learning-augmented online scheduling and neural combinatorial optimization with theoretical guarantees.

Selected research · Computational geometry

Polygon Containment and Partition under Width Constraints

In this dissertation, we study two fundamental optimization problems on polygons: containment and partition problems under width constraints. For containment problems, we develop efficient algorithms for computing the largest inscribed and smallest circumscribed histogons of convex polygons. For partition problems, we consider partitioning a polygon into subpolygons whose widths do not exceed a fixed value and analyze structural properties of the minimum partition number.

Selected problem · largest unit-width rectangle Convex heptagon · drag to change θ
Height surface · h(x, θ) Maximum plateau
The highlighted maximum plateau path follows positions attaining the maximum height at each orientation. It contains nine local maxima, and the highest is the global maximum.
xLeft coordinate θOrientation hRectangle height
Maximum height at each orientation H(θ) = maxx h(x, θ)
Largest rectangle at this orientation 0.0°
1
Corner contact with polygon boundary
Orientation θ0.000 rad Left coordinate x−0.247 Height h3.318
We consider an optimization problem of inscribing a unit rectangle in a convex polygon. The goal is to find a largest unit rectangle inscribed in a convex polygon over all orientations in [0, π). Largest Unit Rectangles Inscribed in a Convex Polygon. Our algorithms find the global optimum in O(n log n + U) time and, output-sensitively, in O(n log n + n/h) time.

02 / Activity

Recent activity

Organizing, talks, and workshops over the past year, most recent first. The full record is in the CV.

  1. Co-organizer · KIAS CAINS

    Center for AI and Natural Sciences Autumn Workshop 2026

    Sono Belle Byeonsan, Buan · Computing for AI, AI for Science, and Math for AI / AI for Math

    workshop

  2. Oral presentation · WAAC 2026

    Orthogonal Strip Partitioning of Simple Polygons: A Lattice-Theoretic Algorithm

    26th Korea–Japan Joint Workshop on Algorithms and Computation · Pusan National University, Busan

    event

  3. Invited participant · KWCG 2026

    26th Korean Workshop on Computational Geometry

    Ruhr University Bochum, Germany

    event

  4. Invited talk · DGIST

    Mathematical Structures in Width-Constrained Polygon Containment and Partitioning

    Theoretical Computer Science Seminar · Daegu Gyeongbuk Institute of Science and Technology, Daegu

  5. Invited lecture · KIAS CAC

    Nearest-Neighbor Search for Scientific Computing

    17th KIAS CAC Summer School on Artificial Intelligence & Parallel Computing · KIAS, Seoul

    school

03 / Featured

Featured papers

Four results in more detail, most recent first. Figures are reproduced from the papers.

Figure 2 SWAT 2026
Vertical trapezoidal decomposition and strip partitions separated by a vertical cut
Vertical trapezoidal decomposition and the strip-merging condition at a cut.

SWAT 2026

Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds

Jaehoon Chung

Minimum orthogonal strip partitions for convex, simple, and self-overlapping polygons, with lattice-based algorithms and matching lower bounds.

Paper arXiv
Figure 1 ISAAC 2025
Windmill polygon with minimum guillotine and non-guillotine trapezoid partitions
A windmill polygon and its minimum guillotine and non-guillotine partitions.

Discrete & Computational Geometry 2026 · ISAAC 2025

Minimum Partition of Polygons under Width and Cut Constraints

Jaehoon Chung, Kazuo Iwama, Chung-Shou Liao, and Hee-Kap Ahn

Minimum polygon partitions under width constraints and restricted cut directions, including guillotine and non-guillotine settings.

Paper Journal
Figure 1 FSTTCS 2022
Five variants of histogons inscribed in or circumscribed around convex polygons
Five inscribed and circumscribed histogon variants considered in the paper.

Computational Geometry 2026 · FSTTCS 2022

Inscribing or Circumscribing a Histogon to a Convex Polygon

Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn

Largest inscribed unit, k-, and unrestricted-width histogons, together with the smallest circumscribed histogon of a convex polygon.

Paper Journal
Figure 1 Computational Geometry 2025
Unit rectangles with five orientations inscribed in the same convex polygon
Unit rectangles in a convex polygon over different orientations.

Computational Geometry 2025

Largest Unit Rectangles Inscribed in a Convex Polygon

Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn

Algorithms for a maximum-area unit-width rectangle over all orientations inside a convex polygon, including an output-sensitive method.

Article

04 / Publications

Publications

Grouped as in the CV, most recent first within each group.

Conference proceedings

Refereed papers in international conference proceedings.

  1. 2026

    Orthogonal Strip Partitioning of Polygons: Lattice-Theoretic Algorithms and Lower Bounds

    Jaehoon Chung

    Proc. 20th Scandinavian Symposium on Algorithm Theory (SWAT)

    paper

  2. 2025

    Minimum Partition of Polygons under Width and Cut Constraints

    Jaehoon Chung, Kazuo Iwama, Chung-Shou Liao, and Hee-Kap Ahn

    Proc. 36th International Symposium on Algorithms and Computation (ISAAC)

    paper

  3. 2022

    Inscribing or Circumscribing a Histogon to a Convex Polygon

    Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn

    Proc. 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS)

    paper

  4. 2022

    Approximating Convex Polygons by Histogons

    Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn

    Proc. 34th Canadian Conference on Computational Geometry (CCCG)

    PDF

Journal articles

Peer-reviewed journal versions, several extending the conference papers above.

  1. 2026

    Minimum Partition of Polygons under Width and Cut Constraints

    Jaehoon Chung, Kazuo Iwama, Chung-Shou Liao, and Hee-Kap Ahn

    Discrete & Computational Geometry · open access

    article

  2. 2026

    Inscribed and Circumscribed Histogons of a Convex Polygon

    Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn

    Computational Geometry: Theory and Applications

    article

  3. 2025

    Largest Unit Rectangles Inscribed in a Convex Polygon

    Jaehoon Chung, Sang Won Bae, Chan-Su Shin, Sang Duk Yoon, and Hee-Kap Ahn

    Computational Geometry: Theory and Applications

    article

Articles

Domestic journal articles.

  1. 2024

    Nearest Neighbor Search Algorithm in Dynamic Environment

    Hee-Kap Ahn, Jaehoon Chung, and Mook Kwon Jung

    Journal of KIISE 42(2)

    article