2026-08-25T17:34:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27179 2026-08-25T13:18:16Z ddc:004 open_access

Algorithm Exercises Skyline and Young Tableau: Divide-and-Conquer Revisited Brodal, Gerth Stølting Divide and conquer marriage before conquest output-sensitive running time We revisit the two classic algorithm exercises skyline and Young tableau, often given to students in an introduction to algorithms course. For both problems we present alternative, still very simple, divide-and-conquer solutions achieving running-times better than what is traditionally asked to achieve in these exercises, in the sense that the running times we achieve are output and input sensitively, respectively. Computing the skyline of a list of n buildings is a classic algorithm problem, solvable with various sweep line and divide-and-conquer approaches in O(nlg n) time. The classic divide-and-conquer solution resembles mergesort, merging skylines of subsets of the buildings. In this paper we describe an alternative simple divide-and-conquer approach (using Kirkpatrick and Seidel’s marriage-before-conquest technique), achieving an optimal output sensitive running time of O(n lg k), where k is the number of buildings contributing to the skyline. For the Young tableau problem, we consider searching rectangular m × n matrices which are both row and column monotone, and where the original problem asks to find an algorithm with running time O(m+n). We present a simple divide-and-conquer algorithm for searching matrices in worst-case optimal running time O(m (1 + lg n/m)), where m ≤ n. We also present an input sensitive search algorithm with optimal running time O(k (1 + lg n/k)), where k is the complexity of the boundary in the matrix between values smaller and larger than the query value (k is the number of vertical line segments on the boundary, where k ≤ m). Here optimality refers to the best possible running time when expressing the running time in terms of m and n, or m, n and k, respectively. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Gerth Stølting Brodal 2026 Is Part Of LIPIcs, Volume 388, 34th Annual European Symposium on Algorithms (ESA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2026.43 urn:nbn:de:0030-drops-271790 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2026.43 eng https://creativecommons.org/licenses/by/4.0/legalcode