Source author record

Eva Rotenberg

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

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Geometry Computer Science and Game Theory Graphics Robotics

Catalog footprint

Research overview

8works

5topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Fully-dynamic $α+ 2$ Arboricity Decomposition and Implicit Colouring

In the implicit dynamic colouring problem, the task is to maintain a representation of a proper colouring as a dynamic graph is subject to insertions and deletions of edges, while facilitating interspersed queries to the colours of vertices. The goal is to use few colours, while still efficiently handling edge-updates and responding to colour-queries. For an n-vertex dynamic graph of arboricity $α$ , we present an algorithm that maintains an implicit vertex colouring with $4\cdot2^α$ colours, in amortised poly- $(\log n)$ update time, and with $O(α log n)$ worst-case query time. The previous best implicit dynamic colouring algorithm uses $2^{40α}$ ) colours, and has a more efficient update time of $O(\log^3 n)$ and the same query time of $O(α log n)$ [Henzinger et al'20]. For graphs undergoing arboricity $α$ preserving updates, we give a fully-dynamic $α+2$ arboricity decomposition in poly $(\log n,α)$ time, which matches the number of forests in the best near-linear static algorithm by Blumenstock and Fischer [2020] who obtain $α+2$ forests in near-linear time. Our construction goes via dynamic bounded out-degree orientations, where we present a fully-dynamic explicit, deterministic, worst-case algorithm for $\lfloor (1+\varepsilon)α\rfloor + 2$ bounded out-degree orientation with update time $O(\varepsilon^{-6}α^2 \log^3 n)$ . The state-of-the-art explicit, deterministic, worst-case algorithm for bounded out-degree orientations maintains a $β\cdot α+ \log_β n$ out-orientation in $O(β^2α^2+βα\log_β n)$ time [Kopelowitz et al'13].

preprint2021arXiv

Best Laid Plans of Lions and Men

We study the following question dating back to J.E. Littlewood (1885-1977): Can two lions catch a man in a bounded area with rectifiable lakes? The lions and the man are all assumed to be points moving with at most unit speed. That the lakes are rectifiable means that their boundaries are finitely long. This requirement is necessary to avoid pathological examples where the man survives forever because any path to the lions is infinitely long. We show that three lions have a winning strategy against a man in a bounded region with finitely many rectifiable lakes. This is "tight" in the sense that there exists a region $R$ in the plane where the man has a strategy to survive forever. We give a rigorous description of such a region $R$ ; a polygonal region with holes whose exterior and interior boundaries are pairwise disjoint, simple polygons. Finally, we consider the following game played on the entire plane instead of a compact region: There is any finite number of unit speed lions and one fast man who can run with speed $1+\varepsilon$ for some value $\varepsilon>0$ . Can the man always survive? We answer the question in the affirmative for any $\varepsilon>0$ . By letting the number of lions tend to infinity, we furthermore show that the man can survive against any countably infinite set of lions.

preprint2021arXiv

Escaping an Infinitude of Lions

We consider the following game played in the Euclidean plane: There is any countable set of unit speed lions and one fast man who can run with speed $1+\varepsilon$ for some value $\varepsilon>0$ . Can the man survive? We answer the question in the affirmative for any $\varepsilon>0$ .

preprint2020arXiv

Skeletonization via Local Separators

We propose a new algorithm for curve skeleton computation which differs from previous algorithms by being based on the notion of local separators. The main benefits of this approach are that it is able to capture relatively fine details and that it works robustly on a range of shape representations. Specifically, our method works on shape representations that can be construed as a spatially embedded graphs. Such representations include meshes, volumetric shapes, and graphs computed from point clouds. We describe a simple pipeline where geometric data is initially converted to a graph, optionally simplified, local separators are computed and selected, and finally a skeleton is constructed. We test our pipeline on polygonal meshes, volumetric shapes, and point clouds. Finally, we compare our results to other methods for skeletonization according to performance and quality.

preprint2016arXiv

Hashing for statistics over k-partitions

In this paper we analyze a hash function for $k$ -partitioning a set into bins, obtaining strong concentration bounds for standard algorithms combining statistics from each bin. This generic method was originally introduced by Flajolet and Martin~[FOCS'83] in order to save a factor $Ω(k)$ of time per element over $k$ independent samples when estimating the number of distinct elements in a data stream. It was also used in the widely used HyperLogLog algorithm of Flajolet et al.~[AOFA'97] and in large-scale machine learning by Li et al.~[NIPS'12] for minwise estimation of set similarity. The main issue of $k$ -partition, is that the contents of different bins may be highly correlated when using popular hash functions. This means that methods of analyzing the marginal distribution for a single bin do not apply. Here we show that a tabulation based hash function, mixed tabulation, does yield strong concentration bounds on the most popular applications of $k$ -partitioning similar to those we would get using a truly random hash function. The analysis is very involved and implies several new results of independent interest for both simple and double tabulation, e.g. a simple and efficient construction for invertible bloom filters and uniform hashing on a given set.

preprint2016arXiv

The Power of Two Choices with Simple Tabulation

The power of two choices is a classic paradigm for load balancing when assigning $m$ balls to $n$ bins. When placing a ball, we pick two bins according to two hash functions $h_0$ and $h_1$ , and place the ball in the least loaded bin. Assuming fully random hash functions, when $m=O(n)$ , Azar et al.~[STOC'94] proved that the maximum load is $\lg \lg n + O(1)$ with high probability. In this paper, we investigate the power of two choices when the hash functions $h_0$ and $h_1$ are implemented with simple tabulation, which is a very efficient hash function evaluated in constant time. Following their analysis of Cuckoo hashing [J.ACM'12], Pǎtraşcu and Thorup claimed that the expected maximum load with simple tabulation is $O(\lg\lg n)$ . This did not include any high probability guarantee, so the load balancing was not yet to be trusted. Here, we show that with simple tabulation, the maximum load is $O(\lg\lg n)$ with high probability, giving the first constant time hash function with this guarantee. We also give a concrete example where, unlike with fully random hashing, the maximum load is not bounded by $\lg \lg n + O(1)$ , or even $(1+o(1))\lg \lg n$ with high probability. Finally, we show that the expected maximum load is $\lg \lg n + O(1)$ , just like with fully random hashing.

preprint2015arXiv

Planar Reachability in Linear Space and Constant Time

We show how to represent a planar digraph in linear space so that distance queries can be answered in constant time. The data structure can be constructed in linear time. This representation of reachability is thus optimal in both time and space, and has optimal construction time. The previous best solution used $O(n\log n)$ space for constant query time [Thorup FOCS'01].

preprint2014arXiv

Faster Fully-Dynamic Minimum Spanning Forest

We give a new data structure for the fully-dynamic minimum spanning forest problem in simple graphs. Edge updates are supported in $O(\log^4n/\log\log n)$ amortized time per operation, improving the $O(\log^4n)$ amortized bound of Holm et al. (STOC'98, JACM'01). We assume the Word-RAM model with standard instructions.

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.

Eva Rotenberg

Research overview

Is this your work?

8 publications

Fully-dynamic $α+ 2$ Arboricity Decomposition and Implicit Colouring

Best Laid Plans of Lions and Men

Escaping an Infinitude of Lions

Skeletonization via Local Separators

Hashing for statistics over k-partitions

The Power of Two Choices with Simple Tabulation

Planar Reachability in Linear Space and Constant Time

Faster Fully-Dynamic Minimum Spanning Forest

See the researcher in context

Building this map preview

Eva Rotenberg

Research overview

Is this your work?

8 publications

Fully-dynamic α+2α+ 2α+2 Arboricity Decomposition and Implicit Colouring

Best Laid Plans of Lions and Men

Escaping an Infinitude of Lions

Skeletonization via Local Separators

Hashing for statistics over k-partitions

The Power of Two Choices with Simple Tabulation

Planar Reachability in Linear Space and Constant Time

Faster Fully-Dynamic Minimum Spanning Forest

See the researcher in context

Building this map preview

Fully-dynamic $α+ 2$ Arboricity Decomposition and Implicit Colouring