Skip to content
CCC Python Course

Convex functions: ternary search and slope sweep

Stage
5
Module
M5.6
Lessons
1

In this module

  • Recognize when a cost function is piecewise-linear and convex.
  • Find the minimum of a convex function using ternary search.
  • Find the minimum by binary search on the slope.
  • Implement the slope-sweep algorithm to find the minimum in O(N log N).

Before this module

M5.5Binary searchM4.2Sorting with keys, and greedy

Lessons

  1. 1Convex functions and ternary search

Practice

Try this on the judge. The link opens the problem on WMOJ.

  1. 2021 S3
    Lunch Concert (opens on WMOJ in a new tab) WMOJ

    Find the best meeting point on a timeline by minimizing total waiting time.

    Why DMOJ: A classic convex-cost problem solved directly by slope sweep.