The number of vertices in order-k abstract color Voronoi diagrams of n sites with m colors is at most 4k(n−k)−2n, proved via colorful Clarkson–Shor and tight bounds on circular sequences of colored permutations.
2022.101900
8 Pith papers cite this work. Polarity classification is still indexing.
8
Pith papers citing it
citation-role summary
background 1
citation-polarity summary
roles
background 1polarities
background 1representative citing papers
Introduces the first algorithmic framework for responsive thematic mapping via layout guides that encode map element sizes and relative positions, demonstrated on rectangular and Demers cartograms.
One-sided local crossing minimization is NP-hard for forests of high-degree stars (with tight ETH lower bound), solvable in quadratic time for degree-2 stars, and admits a 3-approximation via median heuristic with tie-breaking.
A dimension-dependent approximate Carathéodory theorem yields explicit contraction rates for Delaunay mesh refinement that exceed those of standard subdivision.
Feedback vertex set and feedback edge set are NP-complete on directed graphs of maximum degree 3; on planar digraphs, feedback vertex set is polynomial-time solvable if every vertex has indegree at most 1 or outdegree at most 1 and NP-complete otherwise, with tight degree bounds also given for the 3
Improved space-time tradeoffs for visibility polygon queries: O(n^{2+ε}) space for O(log n + k) time, plus better bounds in other regimes using a new polygon decomposition.
Support-weighted partial recentering of maxmin seeds using halfspace depth yields consistent geometric improvement over standard maxmin in planar benchmarks while preserving thresholded H1 summaries.
O(n^3 log n) algorithm computes maximum (weighted) independent sets for disk graphs with all disks on the convex hull, plus O(n^3 log^2 n) for k-dispersion on the same inputs.
citing papers explorer
-
Abstract Color Voronoi Diagrams and Circular Sequences of Color Permutations
The number of vertices in order-k abstract color Voronoi diagrams of n sites with m colors is at most 4k(n−k)−2n, proved via colorful Clarkson–Shor and tight bounds on circular sequences of colored permutations.
-
Automated Responsive Thematic Mapping with Layout Guides
Introduces the first algorithmic framework for responsive thematic mapping via layout guides that encode map element sizes and relative positions, demonstrated on rectangular and Demers cartograms.
-
One-Sided Local Crossing Minimization
One-sided local crossing minimization is NP-hard for forests of high-degree stars (with tight ETH lower bound), solvable in quadratic time for degree-2 stars, and admits a 3-approximation via median heuristic with tie-breaking.
-
Sharp approximate Carath\'eodory theorem and application to iterated Delaunay refinement
A dimension-dependent approximate Carathéodory theorem yields explicit contraction rates for Delaunay mesh refinement that exceed those of standard subdivision.
-
Feedback Set Problems on Bounded-Degree (Planar) Graphs
Feedback vertex set and feedback edge set are NP-complete on directed graphs of maximum degree 3; on planar digraphs, feedback vertex set is polynomial-time solvable if every vertex has indegree at most 1 or outdegree at most 1 and NP-complete otherwise, with tight degree bounds also given for the 3
-
Visibility Queries in Simple Polygons
Improved space-time tradeoffs for visibility polygon queries: O(n^{2+ε}) space for O(log n + k) time, plus better bounds in other regimes using a new polygon decomposition.
-
Local Depth-Based Corrections to Maxmin Landmark Selection for Lazy Witness Persistence
Support-weighted partial recentering of maxmin seeds using halfspace depth yields consistent geometric improvement over standard maxmin in planar benchmarks while preserving thresholded H1 summaries.
-
Maximum Independent Sets in Disk Graphs with Disks in Convex Position
O(n^3 log n) algorithm computes maximum (weighted) independent sets for disk graphs with all disks on the convex hull, plus O(n^3 log^2 n) for k-dispersion on the same inputs.