51 Search Results for "Mount, David M."

Artifact
Software
DOI: 10.4230/artifacts.25998
Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry

Authors: Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, and David M. Mount

Abstract
Cite as

Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, David M. Mount. Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry (Software, Web Application). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-25998,
   title = {{Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry}}, 
   author = {Banerjee, Hridhaan and Brown, Soren and Cagan, June and Gezalyan, Auguste H. and Hunleth, Megan and Kailad, Veena and Kyoung, Chaewoon and Shigeno, Rowan and Tajeddin, Yasmine and Wagger, Andrew and Zhu, Kelin and Mount, David M.},
   note = {Software (visited on 2026-05-27)},
   url = {https://andrew.wagger.net/hilbert/},
   doi = {10.4230/artifacts.25998},
}
Artifact
Audiovisual
DOI: 10.4230/artifacts.25999
Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry

Authors: Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, and David M. Mount

Abstract
Cite as

Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, David M. Mount. Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry (Audiovisual, Video). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-25999,
   title = {{Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry}}, 
   author = {Banerjee, Hridhaan and Brown, Soren and Cagan, June and Gezalyan, Auguste H. and Hunleth, Megan and Kailad, Veena and Kyoung, Chaewoon and Shigeno, Rowan and Tajeddin, Yasmine and Wagger, Andrew and Zhu, Kelin and Mount, David M.},
   note = {Audiovisual (visited on 2026-05-27)},
   url = {https://youtu.be/yhJn--3Qgks},
   doi = {10.4230/artifacts.25999},
}
Artifact
Software
DOI: 10.4230/artifacts.25979
Proximity Alert: Ipelets for Neighborhood Graphs and Clustering

Authors: Gitan Balogh, June Cagan, Bea Fatima, Auguste H. Gezalyan, Danesh Sivakumar, Arushi Srinivasan, Yixuan Sun, Vahe Zaprosyan, and David M. Mount

Abstract
Cite as

Gitan Balogh, June Cagan, Bea Fatima, Auguste H. Gezalyan, Danesh Sivakumar, Arushi Srinivasan, Yixuan Sun, Vahe Zaprosyan, David M. Mount. Proximity Alert: Ipelets for Neighborhood Graphs and Clustering (Software, Source Code). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-25979,
   title = {{Proximity Alert: Ipelets for Neighborhood Graphs and Clustering}}, 
   author = {Balogh, Gitan and Cagan, June and Fatima, Bea and Gezalyan, Auguste H. and Sivakumar, Danesh and Srinivasan, Arushi and Sun, Yixuan and Zaprosyan, Vahe and Mount, David M.},
   note = {Software (visited on 2026-05-27)},
   url = {https://github.com/Otcavo/Ipelets-Full-Library},
   doi = {10.4230/artifacts.25979},
}
Artifact
Audiovisual
DOI: 10.4230/artifacts.25983
Proximity Alert: Ipelets for Neighborhood Graphs and Clustering

Authors: Gitan Balogh, June Cagan, Bea Fatima, Auguste H. Gezalyan, Danesh Sivakumar, Arushi Srinivasan, Yixuan Sun, Vahe Zaprosyan, and David M. Mount

Abstract
Cite as

Gitan Balogh, June Cagan, Bea Fatima, Auguste H. Gezalyan, Danesh Sivakumar, Arushi Srinivasan, Yixuan Sun, Vahe Zaprosyan, David M. Mount. Proximity Alert: Ipelets for Neighborhood Graphs and Clustering (Audiovisual, Video). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-25983,
   title = {{Proximity Alert: Ipelets for Neighborhood Graphs and Clustering}}, 
   author = {Balogh, Gitan and Cagan, June and Fatima, Bea and Gezalyan, Auguste H. and Sivakumar, Danesh and Srinivasan, Arushi and Sun, Yixuan and Zaprosyan, Vahe and Mount, David M.},
   note = {Audiovisual (visited on 2026-05-27)},
   url = {https://youtu.be/NQr-SY1x2qc},
   doi = {10.4230/artifacts.25983},
}
Document
DOI: 10.4230/LIPIcs.SoCG.2026.8
Cauchy’s Surface Area Formula in the Funk Geometry

Authors: Sunil Arya and David M. Mount

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Cauchy’s surface area formula expresses the surface area of a convex body as the average area of its orthogonal projections over all directions. While this tool is fundamental in Euclidean geometry, with applications ranging from geometric tomography to approximation theory, extensions to non-Euclidean settings remain less explored. In this paper, we establish an analog of Cauchy’s formula for the Funk geometry induced by a convex body K in ℝ^d, for the Holmes-Thompson surface area. The formula is based on central projections to boundary points of K. We show that when K is a convex polytope, the formula reduces to a weighted sum of contributions associated with the vertices of K. Finally, as a consequence of our analysis, we derive a generalization of Crofton’s formula for surface areas in the Funk geometry. By viewing Euclidean, Minkowski, Hilbert, and hyperbolic geometries as limiting or special cases of the Funk setting, our results provide a unified framework for these classical surface area formulas.
Cite as

Sunil Arya and David M. Mount. Cauchy’s Surface Area Formula in the Funk Geometry. In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{arya_et_al:LIPIcs.SoCG.2026.8,
  author =	{Arya, Sunil and Mount, David M.},
  title =	{{Cauchy’s Surface Area Formula in the Funk Geometry}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.8},
  URN =		{urn:nbn:de:0030-drops-258140},
  doi =		{10.4230/LIPIcs.SoCG.2026.8},
  annote =	{Keywords: Convexity, Cauchy’s formula, Funk geometry, Hilbert geometry, Crofton’s formula, Holmes-Thompson surface area}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2026.99
Proximity Alert: Ipelets for Neighborhood Graphs and Clustering (Media Exposition)

Authors: Gitan Balogh, June Cagan, Bea Fatima, Auguste H. Gezalyan, Danesh Sivakumar, Arushi Srinivasan, Yixuan Sun, Vahe Zaprosyan, and David M. Mount

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Neighborhood graphs and clustering algorithms are fundamental structures in both computational geometry and data analysis. Visualizing them can help build insight into their behavior and properties. The Ipe extensible drawing editor, developed by Otfried Cheong, is a widely used software system for generating figures. One particular aspect of Ipe is the ability to add Ipelets, which extend its functionality. Here we showcase a set of Ipelets designed to help visualize neighborhood graphs and clustering algorithms. These include: ε-neighbor graphs, furthest-neighbor graphs, Gabriel graphs, k-nearest neighbor graphs, k-th-nearest neighbor graphs, k-mutual neighbor graphs, k-th-mutual neighbor graphs, asymmetric k-nearest neighbor graphs, asymmetric k-th-nearest neighbor graphs, relative-neighbor graphs, sphere-of-influence graphs, Urquhart graphs, Yao graphs, and clustering algorithms including complete-linkage, DBSCAN, HDBSCAN, k-means, k-means++, k-medoids, mean shift, and single-linkage. Our Ipelets are all programmed in Lua and are freely available.
Cite as

Gitan Balogh, June Cagan, Bea Fatima, Auguste H. Gezalyan, Danesh Sivakumar, Arushi Srinivasan, Yixuan Sun, Vahe Zaprosyan, and David M. Mount. Proximity Alert: Ipelets for Neighborhood Graphs and Clustering (Media Exposition). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 99:1-99:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{balogh_et_al:LIPIcs.SoCG.2026.99,
  author =	{Balogh, Gitan and Cagan, June and Fatima, Bea and Gezalyan, Auguste H. and Sivakumar, Danesh and Srinivasan, Arushi and Sun, Yixuan and Zaprosyan, Vahe and Mount, David M.},
  title =	{{Proximity Alert: Ipelets for Neighborhood Graphs and Clustering}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{99:1--99:8},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.99},
  URN =		{urn:nbn:de:0030-drops-259058},
  doi =		{10.4230/LIPIcs.SoCG.2026.99},
  annote =	{Keywords: neighborhood graphs, clustering, proximity graphs, Ipelets, visualization}
}
Document
Media Exposition
DOI: 10.4230/LIPIcs.SoCG.2026.100
Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry (Media Exposition)

Authors: Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, and David M. Mount

Published in: LIPIcs, Volume 367, 42nd International Symposium on Computational Geometry (SoCG 2026)

Abstract
Higher-order Voronoi diagrams and Delaunay mosaics in polygonal metrics have only recently been studied, yet no tools exist for visualizing them. We introduce a tool that fills this gap, providing dynamic interactive software for visualizing higher-order Voronoi diagrams and Delaunay mosaics along with clustering and tools for exploring overlap and outer regions in the Hilbert polygonal metric. We prove that k-th order Voronoi cells are not always star-shaped and establish complexity bounds for our algorithm, which generates all order Voronoi diagrams at once. Our software unifies and extends previous tools for visualizing the Hilbert, Funk, and Thompson geometries.
Cite as

Hridhaan Banerjee, Soren Brown, June Cagan, Auguste H. Gezalyan, Megan Hunleth, Veena Kailad, Chaewoon Kyoung, Rowan Shigeno, Yasmine Tajeddin, Andrew Wagger, Kelin Zhu, and David M. Mount. Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry (Media Exposition). In 42nd International Symposium on Computational Geometry (SoCG 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 367, pp. 100:1-100:6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{banerjee_et_al:LIPIcs.SoCG.2026.100,
  author =	{Banerjee, Hridhaan and Brown, Soren and Cagan, June and Gezalyan, Auguste H. and Hunleth, Megan and Kailad, Veena and Kyoung, Chaewoon and Shigeno, Rowan and Tajeddin, Yasmine and Wagger, Andrew and Zhu, Kelin and Mount, David M.},
  title =	{{Visualizing Higher Order Structures, Overlap Regions, and Clustering in the Hilbert Geometry}},
  booktitle =	{42nd International Symposium on Computational Geometry (SoCG 2026)},
  pages =	{100:1--100:6},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-418-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{367},
  editor =	{Ahn, Hee-Kap and Hoffmann, Michael and Nayyeri, Amir},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2026.100},
  URN =		{urn:nbn:de:0030-drops-259062},
  doi =		{10.4230/LIPIcs.SoCG.2026.100},
  annote =	{Keywords: Hilbert metric, Funk metric, Voronoi diagrams}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.38
Lower Bounds on Tree Covers

Authors: Yu Chen, Zihan Tan, and Hangyu Xu

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
Given an n-point metric space (X,d_X), a tree cover 𝒯 is a set of |𝒯| = k trees on X such that every pair of vertices in X has a low-distortion path in one of the trees in 𝒯. Tree covers have been playing a crucial role in graph algorithms for decades, and the research focus is the construction of tree covers with small size k and distortion. When k = 1, the best distortion is known to be Θ(n). For a constant k ≥ 2, the best distortion upper bound is Õ(n^{1/k}) and the strongest lower bound is Ω(log_k n), leaving a gap to be closed. In this paper, we improve the lower bound to Ω(n^{1/(2^{k-1)}}). Our proof is a novel analysis on a structurally simple grid-like graph, which utilizes some combinatorial fixed-point theorems. We believe that they will prove useful for analyzing other tree-like data structures as well.
Cite as

Yu Chen, Zihan Tan, and Hangyu Xu. Lower Bounds on Tree Covers. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 38:1-38:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{chen_et_al:LIPIcs.ITCS.2026.38,
  author =	{Chen, Yu and Tan, Zihan and Xu, Hangyu},
  title =	{{Lower Bounds on Tree Covers}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{38:1--38:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.38},
  URN =		{urn:nbn:de:0030-drops-253254},
  doi =		{10.4230/LIPIcs.ITCS.2026.38},
  annote =	{Keywords: Tree Covers, Combinatorial Fixed-Point Theorems}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2025.19
Clustering in Varying Metrics

Authors: Deeparnab Chakrabarty, Jonathan Conroy, and Ankita Sarkar

Published in: LIPIcs, Volume 360, 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)

Abstract
We introduce the aggregated clustering problem, where one is given T instances of a center-based clustering task over the same n points, but under different metrics. The goal is to open k centers to minimize an aggregate of the clustering costs - e.g., the average or maximum - where the cost is measured via k-center/median/means objectives. More generally, we minimize a norm Ψ over the T cost values. We show that for T ≥ 3, the problem is inapproximable to any finite factor in polynomial time. For T = 2, we give constant-factor approximations. We also show W[2]-hardness when parameterized by k, but obtain f(k,T)poly(n)-time 3-approximations when parameterized by both k and T. When the metrics have structure, we obtain efficient parameterized approximation schemes (EPAS). If all T metrics have bounded ε-scatter dimension, we achieve a (1+ε)-approximation in f(k,T,ε)poly(n) time. If the metrics are induced by edge weights on a common graph G of bounded treewidth tw, and Ψ is the sum function, we get an EPAS in f(T,ε,tw)poly(n,k) time. Conversely, unless (randomized) ETH is false, any finite factor approximation is impossible if parametrized by only T, even when the treewidth is tw = Ω(polylog n).
Cite as

Deeparnab Chakrabarty, Jonathan Conroy, and Ankita Sarkar. Clustering in Varying Metrics. In 45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 360, pp. 19:1-19:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{chakrabarty_et_al:LIPIcs.FSTTCS.2025.19,
  author =	{Chakrabarty, Deeparnab and Conroy, Jonathan and Sarkar, Ankita},
  title =	{{Clustering in Varying Metrics}},
  booktitle =	{45th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2025)},
  pages =	{19:1--19:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-406-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{360},
  editor =	{Aiswarya, C. and Mehta, Ruta and Roy, Subhajit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2025.19},
  URN =		{urn:nbn:de:0030-drops-251007},
  doi =		{10.4230/LIPIcs.FSTTCS.2025.19},
  annote =	{Keywords: Clustering, approximation algorithms, LP rounding, parameterized and exact algorithms, dynamic programming, fixed parameter tractability, hardness of approximation}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2025.3
Circle-Segment Intersection Queries in Connected Geometric Graphs

Authors: Peyman Afshani, Yannick Bosch, and Sabine Storandt

Published in: LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025)

Abstract
In this paper, we study the problem of efficiently reporting all intersections between a given set of line segments in the plane and a query circle, focusing on the case where the segments form the edges of a connected geometric graph. While previous data structures for circle-segment intersection queries on general segment sets incur high space or query time costs, we exploit the connectivity of the input to obtain significantly improved performance. In fact, we propose a new circle-segment intersection data structure that can be constructed in 𝒪((n + C) log³ n) time and space on connected graphs with n edges and C edge crossings. It answers intersection queries in 𝒪(k log³ n) time, where k denotes the output size. Our method relies on the construction of efficient circle-graph intersection oracles as well as a novel linear-time algorithm to partition the edges of the graph into balanced, connected components, which might be of independent interest. In a proof-of-concept experimental study on real-world road networks, we show that our novel data structure also performs well in practice. Even on networks with millions of edges, the construction time is within minutes and queries are answered in a few milliseconds.
Cite as

Peyman Afshani, Yannick Bosch, and Sabine Storandt. Circle-Segment Intersection Queries in Connected Geometric Graphs. In 36th International Symposium on Algorithms and Computation (ISAAC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 359, pp. 3:1-3:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{afshani_et_al:LIPIcs.ISAAC.2025.3,
  author =	{Afshani, Peyman and Bosch, Yannick and Storandt, Sabine},
  title =	{{Circle-Segment Intersection Queries in Connected Geometric Graphs}},
  booktitle =	{36th International Symposium on Algorithms and Computation (ISAAC 2025)},
  pages =	{3:1--3:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-408-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{359},
  editor =	{Chen, Ho-Lin and Hon, Wing-Kai and Tsai, Meng-Tsung},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.3},
  URN =		{urn:nbn:de:0030-drops-249114},
  doi =		{10.4230/LIPIcs.ISAAC.2025.3},
  annote =	{Keywords: Intersection data structure, Graph partitioning, Dobkin-Kirkpatrick hierarchy}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.25
Covering a Few Submodular Constraints and Applications

Authors: Tanvi Bajpai, Chandra Chekuri, and Pooja Kulkarni

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
We consider the problem of covering multiple submodular constraints. Given a finite ground set N, a cost function c: N → ℝ_+, r monotone submodular functions f_1,f_2,…,f_r over N and requirements b_1,b_2,…,b_r the goal is to find a minimum cost subset S ⊆ N such that f_i(S) ≥ b_i for 1 ≤ i ≤ r. When r = 1 this is the well-known Submodular Set Cover problem. Previous work [Chekuri et al., 2022] considered the setting when r is large and developed bi-criteria approximation algorithms, and approximation algorithms for the important special case when each f_i is a weighted coverage function. These are fairly general models and capture several concrete and interesting problems as special cases. The approximation ratios for these problem are at least Ω(log r) which is unavoidable when r is part of the input. In this paper, motivated by some recent applications, we consider the problem when r is a fixed constant and obtain two main results. When the f_i are weighted coverage functions from a deletion-closed set system we obtain a (1+ε)(e/(e-1))(1+β)-approximation where β is the approximation ratio for the underlying set cover instances via the natural LP. Second, for covering multiple submodular constraints we obtain a randomized bi-criteria approximation algorithm that for any given integer α ≥ 1 outputs a set S such that f_i(S) ≥ (1-1/e^α-ε)b_i for each i ∈ [r] and 𝔼[c(S)] ≤ (1+ε)α ⋅ OPT. These results show that one can obtain nearly as good an approximation for any fixed r as what one would achieve for r = 1. We also demonstrate applications of our results to implicit covering problems such as fair facility location.
Cite as

Tanvi Bajpai, Chandra Chekuri, and Pooja Kulkarni. Covering a Few Submodular Constraints and Applications. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 25:1-25:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bajpai_et_al:LIPIcs.APPROX/RANDOM.2025.25,
  author =	{Bajpai, Tanvi and Chekuri, Chandra and Kulkarni, Pooja},
  title =	{{Covering a Few Submodular Constraints and Applications}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{25:1--25:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.25},
  URN =		{urn:nbn:de:0030-drops-243917},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.25},
  annote =	{Keywords: covering, linear programming, rounding, fairness}
}
Document
DOI: 10.4230/OASIcs.ICPEC.2025.10
Standards-Based Grading in Undergraduate Courses for Technology Majors

Authors: Ruth Lamprecht, Jonathan McCurdy, Melanie Butler, Brian Heinold, and Daniel Salinas Duron

Published in: OASIcs, Volume 133, 6th International Computer Programming Education Conference (ICPEC 2025)

Abstract
This paper outlines the methods employed by several instructors within a single department to implement standards-based assessments. The authors began integrating standards across multiple courses in their computer science, cybersecurity, data science, and mathematics programs. This shift was driven by a desire to promote equity in grading and to address the growing influence of artificial intelligence, which can obscure a student’s true understanding. In this work, the authors examine the supporting research that guided their motivation and informed their implementation of various grading techniques. With an emphasis on courses involving technology, they also detail the processes they use to manage the new assessments, provide examples of assessment questions, and share key lessons learned in making this transition successful for both instructors and students. This work addresses a significant gap in the literature, as there appears to be a notable lack of resources on the application of standards-based grading in technical disciplines.
Cite as

Ruth Lamprecht, Jonathan McCurdy, Melanie Butler, Brian Heinold, and Daniel Salinas Duron. Standards-Based Grading in Undergraduate Courses for Technology Majors. In 6th International Computer Programming Education Conference (ICPEC 2025). Open Access Series in Informatics (OASIcs), Volume 133, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lamprecht_et_al:OASIcs.ICPEC.2025.10,
  author =	{Lamprecht, Ruth and McCurdy, Jonathan and Butler, Melanie and Heinold, Brian and Salinas Duron, Daniel},
  title =	{{Standards-Based Grading in Undergraduate Courses for Technology Majors}},
  booktitle =	{6th International Computer Programming Education Conference (ICPEC 2025)},
  pages =	{10:1--10:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-393-5},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{133},
  editor =	{Queir\'{o}s, Ricardo and Pinto, M\'{a}rio and Portela, Filipe and Sim\~{o}es, Alberto},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ICPEC.2025.10},
  URN =		{urn:nbn:de:0030-drops-240408},
  doi =		{10.4230/OASIcs.ICPEC.2025.10},
  annote =	{Keywords: Alternative Grading, Standards-Based Grading, Computer Science}
}
Document
APPROX
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.8
Multipass Linear Sketches for Geometric LP-Type Problems

Authors: N. Efe Çekirge, William Gay, and David P. Woodruff

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract
LP-type problems such as the Minimum Enclosing Ball (MEB), Linear Support Vector Machine (SVM), Linear Programming (LP), and Semidefinite Programming (SDP) are fundamental combinatorial optimization problems, with many important applications in machine learning applications such as classification, bioinformatics, and noisy learning. We study LP-type problems in several streaming and distributed big data models, giving ε-approximation linear sketching algorithms with a focus on the high accuracy regime with low dimensionality d, that is, when d < (1/ε)^0.999. Our main result is an O(ds) pass algorithm with O(s(√d/ε)^{3d/s}) ⋅ poly(d, log (1/ε)) space complexity in words, for any parameter s ∈ [1, d log (1/ε)], to solve ε-approximate LP-type problems of O(d) combinatorial and VC dimension. Notably, by taking s = d log (1/ε), we achieve space complexity polynomial in d and polylogarithmic in 1/ε, presenting exponential improvements in 1/ε over current algorithms. We complement our results by showing lower bounds of (1/ε)^Ω(d) for any 1-pass algorithm solving the (1 + ε)-approximation MEB and linear SVM problems, further motivating our multi-pass approach.
Cite as

N. Efe Çekirge, William Gay, and David P. Woodruff. Multipass Linear Sketches for Geometric LP-Type Problems. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 8:1-8:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cekirge_et_al:LIPIcs.APPROX/RANDOM.2025.8,
  author =	{\c{C}ekirge, N. Efe and Gay, William and Woodruff, David P.},
  title =	{{Multipass Linear Sketches for Geometric LP-Type Problems}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{8:1--8:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.8},
  URN =		{urn:nbn:de:0030-drops-243741},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.8},
  annote =	{Keywords: Streaming, sketching, LP-type problems}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.3
Support Vector Machines in the Hilbert Geometry

Authors: Aditya Acharya, Auguste H. Gezalyan, Julian Vanecek, David M. Mount, and Sunil Arya

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Support Vector Machines (SVMs) are a class of classification models in machine learning that are based on computing a maximum-margin separator between two sets of points. The SVM problem has been heavily studied for Euclidean geometry and for a number of kernels. In this paper, we consider the linear SVM problem in the Hilbert metric, a non-Euclidean geometry defined over a convex body. We present efficient algorithms for computing the SVM classifier for a set of n points in the Hilbert metric defined by convex polygons in the plane and convex polytopes in d-dimensional space. We also consider the problems in the related Funk distance.
Cite as

Aditya Acharya, Auguste H. Gezalyan, Julian Vanecek, David M. Mount, and Sunil Arya. Support Vector Machines in the Hilbert Geometry. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 3:1-3:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{acharya_et_al:LIPIcs.WADS.2025.3,
  author =	{Acharya, Aditya and Gezalyan, Auguste H. and Vanecek, Julian and Mount, David M. and Arya, Sunil},
  title =	{{Support Vector Machines in the Hilbert Geometry}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{3:1--3:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.3},
  URN =		{urn:nbn:de:0030-drops-242348},
  doi =		{10.4230/LIPIcs.WADS.2025.3},
  annote =	{Keywords: Support vector machines, Hilbert geometry, linear classification, machine learning, LP-type problems}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.4
Evolving Distributions Under Local Motion

Authors: Aditya Acharya and David M. Mount

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Geometric data sets that arise in modern applications are often very large and change dynamically over time. A popular framework for dealing with such data sets is the evolving data framework, where a discrete structure continuously varies over time due to the unseen actions of an evolver, which makes small changes to the data. An algorithm probes the current state through an oracle, and the objective is to maintain a hypothesis of the data set’s current state that is close to its actual state at all times. In this paper, we apply this framework to maintaining a set of n point objects in motion in d-dimensional Euclidean space. To model the uncertainty in the object locations, both the ground truth and hypothesis are based on spatial probability distributions, and the distance between them is measured by the Kullback-Leibler divergence (relative entropy). We introduce a simple and intuitive motion model in which, with each time step, the distance that any object can move is a fraction of the distance to its nearest neighbor. We present an algorithm that, in steady state, guarantees a distance of O(n) between the true and hypothesized placements. We also show that for any algorithm in this model, there is an evolver that can generate a distance of Ω(n), implying that our algorithm is asymptotically optimal.
Cite as

Aditya Acharya and David M. Mount. Evolving Distributions Under Local Motion. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 4:1-4:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{acharya_et_al:LIPIcs.WADS.2025.4,
  author =	{Acharya, Aditya and Mount, David M.},
  title =	{{Evolving Distributions Under Local Motion}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{4:1--4:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.4},
  URN =		{urn:nbn:de:0030-drops-242357},
  doi =		{10.4230/LIPIcs.WADS.2025.4},
  annote =	{Keywords: Evolving data, tracking, imprecise points, local-motion model, online algorithms}
}
  • Refine by Type
  • 45 Document/PDF
  • 26 Document/HTML
  • 6 Artifact

  • Refine by Publication Year
  • 8 2026
  • 27 2025
  • 2 2024
  • 3 2023
  • 3 2021
  • Show More...

  • Refine by Author
  • 28 Mount, David M.
  • 14 Gezalyan, Auguste H.
  • 7 Arya, Sunil
  • 6 Cagan, June
  • 5 Banerjee, Hridhaan
  • Show More...

  • Refine by Series/Journal
  • 43 LIPIcs
  • 1 OASIcs
  • 1 LITES

  • Refine by Classification
  • 29 Theory of computation → Computational geometry
  • 3 Theory of computation → Facility location and clustering
  • 3 Theory of computation → Sketching and sampling
  • 2 Applied computing → Bioinformatics
  • 2 Software and its engineering → Just-in-time compilers
  • Show More...

  • Refine by Keyword
  • 7 Hilbert metric
  • 5 Macbeath regions
  • 5 convexity
  • 3 Approximation algorithms
  • 3 Hilbert geometry
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact