Personal tools
You are here: Home Courses Workshop Fall 2019/2020 Workshop: Geometric Optimization Challenge
« December 2019 »
Log in

Forgot your password?

Workshop: Geometric Optimization Challenge

Workshop (sadna) 

Fall 2019/2020


Course hours: Wednesday, 11:00 - 13:00
Location: Schreiber 008

Instructor: Dan Halperin, danha AT post tau ac il

Teaching assistants: Michal Kleinbort, balasmic AT post tau ac il

General information: In 2020 for the second time the central conference in Computational Geometry, SoCG, will hold a software contest in the area of Geometric Optimization.

The challenge is: Given a set S of n points in the plane. The objective is to compute a plane graph with vertex set S (with each point in S having positive degree) that partitions the convex hull of S into the smallest possible number of convex faces.

The organizers supply many input examples of varying size as well as a testing and scoring program. In the workshop we will use this platform to learn about geometric algorithms, how to correctly and efficiently code them, massive parallelization, metaheuristics and more. 

The workshop teams will participate in the contest.

During the first few (two-three) weeks of the semester, we will have meetings of the sadna (Wednesday 11:00-13:00) to describe the problem and available tools. On the third meeting you will have to submit a short document (one page) with a brief plan of work, together with the names and ID numbers of your teammates.

We will then meet roughly once a month to report on progress and discuss issues that arise in the work. More details on those meetings, the milestones when you should submit reports, and more will appear in this web-site as the project progresses.
The recommended team size is three students.


Algorithms, Data structures, Software1

Meetings and milestones

  • Wednesday 30/10/19, 6/11/19: the problem and available tools
  • Wednesday 13/11/19: submission of team composition and a brief work-plan

More on the 2019 Contest

You can get an impression of the spirit of the contest by browsing last year's website:


The team at the Computational Geometry lab at TAU participated in last year's challenge, which was to generate a polygon that goes through n given input points, with either minimal or maximal area. The team was awarded the third prize. Below is a result obtained for n = 2000, with points distributed randomly in a square.



Document Actions