Output-Sensitive Algorithms for Geometric and Combinatorial Structures

This direction is no longer present in the current build. Its last version stays readable and citable here.

Version 1 of 143 papers66 conceptsfrozen 2026-10-04

In traditional complexity theory, we typically measure an algorithm's efficiency by how its runtime scales with the size of the input, $n$. However, in many geometric and combinatorial problems, the "worst-case" scenario is a poor reflection of reality. A 3D arrangement of triangles might theoretically have cubic complexity, but in practice, the triangles may barely touch. A Voronoi diagram in high dimensions could have an exponential number of faces, yet for many real-world datasets, the resulting structure is remarkably sparse.

The research direction of output-sensitivity shifts the focus: it seeks algorithms whose performance is proportional to the size of the result ($f$) rather than the theoretical maximum possible output. This approach ensures that if the answer is simple, the computation is fast.

The Intuition of Redundancy

The fundamental motivation for output-sensitivity is the observation that most data points in a large set are often "internal" or redundant to the final solution.

In Archetypal Analysis or the Smallest Enclosing Ball problem, the final geometric representation is defined entirely by a few "extreme" or boundary points. Braxton Osting and Yiming Xu 0009 demonstrate in Probabilistic methods for approximate archetypal analysis that processing every observation in a massive dataset is computationally wasteful. Similarly, Ya-Feng Liu and colleagues show that by ignoring redundant interior points during heavy computation phases, algorithms for the Smallest Enclosing Ball problem can achieve order-of-magnitude speedups.

Vertex Oracles: Avoiding the Intermediate Mess

A recurring challenge in high-dimensional geometry is that intermediate structures can be exponentially larger than both the input and the final output. For example, computing the projection of a "resultant polytope"—a key task in algebraic geometry—traditionally required constructing massive secondary polytopes.

To bypass this, researchers like Ioannis Emiris, Vissarion Fisikopoulos, and Christos Konaxis introduced the concept of a vertex oracle. Instead of building the entire high-dimensional object, the algorithm uses an optimization oracle to "probe" the space, identifying only the extreme vertices in specific directions. As detailed in An Oracle-based, Output-sensitive Algorithm for Projections of Resultant Polytopes, this allows the algorithm to construct the final convex hull incrementally, scaling its work directly with the number of vertices in the final output.

Scaling with Intersections and Tangents

In spatial partitioning and pathfinding, the complexity of the environment is often defined by how objects interact (intersections) rather than how many objects there are.

  • Voronoi Diagrams: Standard algorithms often reduce Voronoi construction to higher-dimensional convex hulls, which is inefficient if the output is small. Gary L. Miller and Donald R. Sheehy developed MeshVoronoi, an algorithm that achieves a runtime of $O(f \log n \log \Delta)$, where $f$ is the number of faces in the final output. This ensures efficiency in high dimensions where the output size varies drastically.
  • Pathfinding: When navigating among curved obstacles, the "visibility graph" determines the shortest path. In Computing Shortest Paths among Curved Obstacles in the Plane, the authors show that complexity should scale with the number of free common tangents between obstacles. In sparse environments, this is much smaller than the total number of vertices defining the obstacle boundaries.
  • Boolean Operations: For operations on polygons with circular arcs, Xiao Lin proposed the RE2L algorithm, which focuses only on "related edges" involved in intersections, outperforming general libraries by an order of magnitude.

Redefining Hardness

Output-sensitivity also forces a re-evaluation of what makes a problem "hard." In multiobjective optimization, the set of optimal solutions (the Pareto front) can be exponentially large. Fritz Bökler and Petra Mutzel argue in Output-sensitive Complexity of Multiobjective Combinatorial Optimization that we must distinguish between problems that are slow because the output is huge and those that are fundamentally difficult to compute.

By measuring runtime as a function of both input ($n$) and output ($f$), researchers can identify "efficient" algorithms for problems like the multiobjective global min-cut, which might otherwise be dismissed under traditional complexity frameworks. This perspective is echoed in graph theory by Surya Mathialagan and Virginia Vassilevska Williams, who seek optimal output-sensitive clique listing to ensure that finding rare structures in a graph doesn't cost as much as finding common ones.

Papers in this version

History & citationVersion 1 · 2026-10-04

No longer present in the current build · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_output_sensitive_algorithms_for_geometri_061905eb,
  title = {Output-Sensitive Algorithms for Geometric and Combinatorial Structures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/output-sensitive-algorithms-for-geometric-and-combinatorial-structures/rdr_061905ebd4f54860aeadaa2738adaedb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_output_sensitive_algorithms_for_geometri_061905eb_v1,
  title = {Output-Sensitive Algorithms for Geometric and Combinatorial Structures},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/output-sensitive-algorithms-for-geometric-and-combinatorial-structures/rdr_061905ebd4f54860aeadaa2738adaedb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}