Demonstration venue · read-only. Every page can be browsed; the buttons that would change it are switched off. Create an account to run TaxoReview on your own data.

Roza Pogalnikova

dblp:97/9733 · DBLP profile ↗
← Back
2ranked-venue papers
0as first author
0since 2021 · last 2012
—ORCID · none

Domains — the database's venue-derived domains; a paper can count in several

Graphics, computer vision, multimedia, augmented reality and games · 1Theory of computation · 1

Expertise — from the expertise taxonomy: the topics of the expert's papers under the CCF categories. A weight counts papers with recency: 1 for a paper about the topic, 0.3 when the topic is its context, halved every five years.

Theoretical computer science
1 paper
Computational geometry · 100%

Topics — the 2 heaviest of 2, each with the papers that count most for it

TopicWeightPapersLastEvidence papers
Computational geometry › geometric modeling and processing
minkowski sum
0.112011
Deconstructing approximate offsets · SCG 2011
Computational geometry › shape analysis
shape approximation
0.112011
Deconstructing approximate offsets · SCG 2011

Methods — techniques the papers use, named apart from their topics

rational arithmetic · 0.1exact decision algorithm · 0.1
YearPublicationVenuePosition
2012 Deconstructing Approximate Offsets
Eric Berberich, Dan Halperin, Michael Kerber, Roza Pogalnikova
Discret. Comput. Geom.4
2011 Deconstructing approximate offsets
abstract
We consider the offset-deconstruction problem: Given a polygonal shape Q with n vertices, can it be expressed, up to a tolerance µ in Hausdorff distance, as the Minkowski sum of another polygonal shape P with a disk of fixed radius? If it does, we also seek a preferably simple-looking solution shape P; then, P's offset constitutes an accurate, vertex-reduced, and smoothened approximation of Q. We give an O(n log n)-time exact decision algorithm that handles any polygonal shape, assuming the real-RAM model of computation. An alternative algorithm, based purely on rational arithmetic, answers the same deconstruction problem, up to an uncertainty parameter, and its running time depends on the parameter δ (in addition to the other input parameters: n, δ and the radius of the disk). If the input shape is found to be approximable, the rational-arithmetic algorithm also computes an approximate solution shape for the problem. For convex shapes, the complexity of the exact decision algorithm drops to O(n), which is also the time required to compute a solution shape P with at most one more vertex than a vertex-minimal one. Our study is motivated by applications from two different domains. However, since the offset operation has numerous uses, we anticipate that the reverse question that we study here will be still more broadly applicable. We present results obtained with our implementation of the rational-arithmetic algorithm.
Eric Berberich, Dan Halperin, Michael Kerber, Roza Pogalnikova
SCG4