BZPEERReading, trust and collaboration for research
Menu

Discover

GraphFollow connections around a paper, topic or saved view.

Workspaces

HomePick up where your research flow left off.InboxHandle requests, replies and notifications from one place.CollectionsCurate reading lists, evidence sets and shareable dossiers.ResearchSee your private provenance graph, trail and imports.CollaborationMove from discovery into focused discussion rooms.PublishDraft, preview and publish full-text research articles.

Network

ExpertsFind specialists worth following or asking for help.CommunitiesJoin research circles organized around shared work.PartnersSee external organizations active around the same topics.

Opportunities

ListingsBrowse roles, calls and collaborations with clearer fit signals.

Account

Log inReturn to your reading and collaboration workspace.Create accountStart saving work, following people and joining teams.
Log inCreate account

Researcher profile

Justin Dallant

Justin Dallant contributes to research discovery and scholarly infrastructure.

ResearcherAffiliation not importedOpen to collaborate
Computational Geometry

Trust snapshot

Quick read

Trust 15 - UnverifiedVerification L1Unclaimed author
3works
0followers
1topics
2close collaborators

Actions

Decide how to stay connected

Follow researcher0

Identity and collaboration

How to connect with this researcher

Claiming links this public author record to a researcher profile and unlocks direct collaboration workflows.

Log in to claim

Direct collaboration

Open a focused conversation when the fit is right

Claim this author entity first to unlock direct invitations.

Research graph

See the researcher in context

Open full explorer

Inspect adjacent work, topics, institutions and collaborators without jumping out to a separate graph page.

Building this graph slice

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

Published work

3 published item(s)

preprint2022arXiv

Conditional Lower Bounds for Dynamic Geometric Measure Problems

We give new polynomial lower bounds for a number of dynamic measure problems in computational geometry. These lower bounds hold in the Word-RAM model, conditioned on the hardness of either 3SUM, APSP, or the Online Matrix-Vector Multiplication problem [Henzinger et al., STOC 2015]. In particular we get lower bounds in the incremental and fully-dynamic settings for counting maximal or extremal points in R^3, different variants of Klee's Measure Problem, problems related to finding the largest empty disk in a set of points, and querying the size of the i'th convex layer in a planar set of points. We also answer a question of Chan et al. [SODA 2022] by giving a conditional lower bound for dynamic approximate square set cover. While many conditional lower bounds for dynamic data structures have been proven since the seminal work of Patrascu [STOC 2010], few of them relate to computational geometry problems. This is the first paper focusing on this topic. Most problems we consider can be solved in O(n log n) time in the static case and their dynamic versions have only been approached from the perspective of improving known upper bounds. One exception to this is Klee's measure problem in R^2, for which Chan [CGTA 2010] gave an unconditional $Ω(\sqrt{n})$ lower bound on the worst-case update time. By a similar approach, we show that such a lower bound also holds for an important special case of Klee's measure problem in R^3 known as the Hypervolume Indicator problem, even for amortized runtime in the incremental setting.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

How Fast Can We Play Tetris Greedily With Rectangular Pieces?

Consider a variant of Tetris played on a board of width $w$ and infinite height, where the pieces are axis-aligned rectangles of arbitrary integer dimensions, the pieces can only be moved before letting them drop, and a row does not disappear once it is full. Suppose we want to follow a greedy strategy: let each rectangle fall where it will end up the lowest given the current state of the board. To do so, we want a data structure which can always suggest a greedy move. In other words, we want a data structure which maintains a set of $O(n)$ rectangles, supports queries which return where to drop the rectangle, and updates which insert a rectangle dropped at a certain position and return the height of the highest point in the updated set of rectangles. We show via a reduction to the Multiphase problem [Pătraşcu, 2010] that on a board of width $w=Θ(n)$, if the OMv conjecture [Henzinger et al., 2015] is true, then both operations cannot be supported in time $O(n^{1/2-ε})$ simultaneously. The reduction also implies polynomial bounds from the 3-SUM conjecture and the APSP conjecture. On the other hand, we show that there is a data structure supporting both operations in $O(n^{1/2}\log^{3/2}n)$ time on boards of width $n^{O(1)}$, matching the lower bound up to a $n^{o(1)}$ factor.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Efficiently stabbing convex polygons and variants of the Hadwiger-Debrunner $(p, q)$-theorem

Hadwiger and Debrunner showed that for families of convex sets in $\mathbb{R}^d$ with the property that among any $p$ of them some $q$ have a common point, the whole family can be stabbed with $p-q+1$ points if $p \geq q \geq d+1$ and $(d-1)p < d(q-1)$. This generalizes a classical result by Helly. We show how such a stabbing set can be computed for a family of convex polygons in the plane with a total of $n$ vertices in $O((p-q+1)n^{4/3}\log^{8} n(\log\log n)^{1/3} + np^2)$ expected time. For polyhedra in $\mathbb{R}^3$, we get an algorithm running in $O((p-q+1)n^{5/2}\log^{10} n(\log\log n)^{1/6} + np^3)$ expected time. We also investigate other conditions on convex polygons for which our algorithm can find a fixed number of points stabbing them. Finally, we show that analogous results of the Hadwiger and Debrunner $(p,q)$-theorem hold in other settings, such as convex sets in $\mathbb{R}^d\times\mathbb{Z}^k$ or abstract convex geometries.

0 citations0 reviewsNo code linkedOpen access