Erik Krohn

Dr. Erik Krohn

Department of Computer Science, University of Wisconsin, Oshkosh, WI, 54901, USA

Research Focus & Metrics

Academic Career Length

15Years (2012-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
6 June 2012 in Algorithmica
Verified
Journal Article
Closed access
PDF file
EKErik Krohn
Erik Krohn
BNBengt J. Nilsson
Bengt J. Nilsson

11 January 2025 in Algorithmica
Verified
Journal Article
Open access
PDF file
OFOmrit Filtser
Omrit Filtser
EKErik Krohn
Erik Krohn
BNBengt J. Nilsson
Bengt J. Nilsson
CRChristian Rieck
Christian Rieck
CSChristiane Schmidt
Christiane Schmidt
We study the Art Gallery Problem under k-hop visibility in polyominoes. In this visibility model, two unit squares of a polyomino can see each other if and only if the shortest path between the respective vertices in the dual graph of the polyomino has length at most k. In this paper, we show that the VC dimension of this problem is 3 in simple polyominoes, and 4 in polyominoes with holes. Furthermore, we provide a reduction from Planar Monotone 3Sat, thereby showing that the problem is -complete even in thin polyominoes (i.e., polyominoes that do not a contain a $$2\times 2$$ 2 × 2 block of cells). Complementarily, we present a linear-time 4-approximation algorithm for simple 2-thin polyominoes (which do not contain a $$3\times 3$$ 3 × 3 block of cells) for all $$k\in {\mathbb {N}}$$ k ∈ N .

24 October 2018 in Computational Geometry
Verified
Journal Article
Closed access
MGMatt Gibson
Matt Gibson
EKErik Krohn
Erik Krohn
QWQing Wang
Qing Wang

29 October 2022
Verified
Book Chapter
Closed access
PDF file
HHHannah Miller Hillberg
Hannah Miller Hillberg
EKErik Krohn
Erik Krohn
APAlex Pahlow
Alex Pahlow

6 March 2024
Verified
Book Chapter
Closed access
PDF file
OFOmrit Filtser
Omrit Filtser
EKErik Krohn
Erik Krohn
BNBengt J. Nilsson
Bengt J. Nilsson
CRChristian Rieck
Christian Rieck
CSChristiane Schmidt
Christiane Schmidt

9 December 2023
Verified
Book Chapter
Closed access
PDF file
EKErik Krohn
Erik Krohn
APAlex Pahlow
Alex Pahlow
ZYZhongxiu Yang
Zhongxiu Yang