Source author record

Georg Osang

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Geometry Discrete Mathematics math.AT math.CO

Catalog footprint

Research overview

2works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Computing the Multicover Bifiltration

Given a finite set $A\subset\mathbb{R}^d$ , let Cov $_{r,k}$ denote the set of all points within distance $r$ to at least $k$ points of $A$ . Allowing $r$ and $k$ to vary, we obtain a 2-parameter family of spaces that grow larger when $r$ increases or $k$ decreases, called the \emph{multicover bifiltration}. Motivated by the problem of computing the homology of this bifiltration, we introduce two closely related combinatorial bifiltrations, one polyhedral and the other simplicial, which are both topologically equivalent to the multicover bifiltration and far smaller than a \v Cech-based model considered in prior work of Sheehy. Our polyhedral construction is a bifiltration of the rhomboid tiling of Edelsbrunner and Osang, and can be efficiently computed using a variant of an algorithm given by these authors. Using an implementation for dimension 2 and 3, we provide experimental results. Our simplicial construction is useful for understanding the polyhedral construction and proving its correctness.

preprint2012arXiv

Fork-forests in bi-colored complete bipartite graphs

Motivated by the problem in [6], which studies the relative efficiency of propositional proof systems, 2-edge colorings of complete bipartite graphs are investigated. It is shown that if the edges of $G=K_{n,n}$ are colored with black and white such that the number of black edges differs from the number of white edges by at most 1, then there are at least $n(1-1/\sqrt{2})$ vertex-disjoint forks with centers in the same partite set of $G$ . Here, a fork is a graph formed by two adjacent edges of different colors. The bound is sharp. Moreover, an algorithm running in time $O(n^2 \log n \sqrt{n α(n^2,n) \log n})$ and giving a largest such fork forest is found.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.