Arrow Research search

Author name cluster

Therese Biedl

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

5 papers
1 author row

Possible papers

5

I&C Journal 2026 Journal Article

Computing conforming partitions with low stabbing number for rectilinear polygons

  • Therese Biedl
  • Stephane Durocher
  • Debajyoti Mondal
  • Rahnuma Islam Nishat
  • Bastien Rivier

A conforming partition of a rectilinear n-gon P (possibly with holes) is a partition of P into rectangles without using Steiner points (i. e. , all corners of all rectangles must lie on the boundary of P). The stabbing number of such a partition is the maximum number of rectangles intersected by an axis-aligned segment lying in the interior of P. In this paper, we examine the problem of computing conforming partitions with low stabbing number. We show that computing a conforming partition with stabbing number at most 4 is NP -hard, which strengthens a previously known hardness result [Durocher & Mehrabi, Theor. Comput. Sci. 689: 157-168 (2017)] and eliminates the possibility for fixed-parameter-tractable algorithms parameterized by the stabbing number unless P = NP. In contrast, we give (i) an O ( n log ⁡ n ) -time algorithm to decide whether a conforming partition with stabbing number 2 exists, (ii) a fixed-parameter-tractable algorithm parameterized by both the stabbing number and treewidth of the pixel graph of the polygon, and (iii) a fixed-parameter-tractable algorithm parameterized by the stabbing number for polygons without holes in general position.

Details DOI

TCS Journal 2011 Journal Article

Reconstructing polygons from scanner data

  • Therese Biedl
  • Stephane Durocher
  • Jack Snoeyink

A range-finding scanner can collect information about the shape of an (unknown) polygonal room in which it is placed. Suppose that a set of scanners returns not only a set of points, but also additional information, such as the normal to the plane when a scan beam detects a wall. We consider the problem of reconstructing the floor plan of a room from different types of scan data. In particular, we present algorithmic and hardness results for reconstructing two-dimensional polygons from point-wall pairs, point-normal pairs, and visibility polygons. The polygons may have restrictions on topology (e. g. , to be simply connected) or geometry (e. g. , to be orthogonal). We show that this reconstruction problem is NP-hard under most models, but that some restrictive assumptions do allow polynomial-time reconstruction algorithms.

Details DOI

TCS Journal 2010 Journal Article

Reconstructing h v -convex multi-coloured polyominoes

  • Adam Bains
  • Therese Biedl

In this paper, we consider the problem of reconstructing polyominoes from information about the thickness in vertical and horizontal directions. We focus on the case where there are multiple disjoint polyominoes (of different colours) that are h v -convex, i. e. , any intersection with a horizontal or vertical line is contiguous. We show that reconstruction of such polyominoes is polynomial if the number of colours is constant, but NP-hard for an unbounded number of colours.

Details DOI

TCS Journal 2004 Journal Article

Finding hidden independent sets in interval graphs

  • Therese Biedl
  • Broňa Brejová
  • Erik D. Demaine
  • Angèle M. Hamel
  • Alejandro López-Ortiz
  • Tomáš Vinař

We design efficient competitive algorithms for discovering hidden information using few queries. Specifically, consider a game in a given set of intervals (and their implied interval graph G) in which our goal is to discover an (unknown) independent set X by making the fewest queries of the form “Is point p covered by an interval in X? ” Our interest in this problem stems from two applications: experimental gene discovery with PCR technology and the game of Battleship (in a 1-dimensional setting). We provide adaptive algorithms for both the verification scenario (given an independent set, is it X?) and the discovery scenario (find X without any information). Under some assumptions, these algorithms use an asymptotically optimal number of queries in every instance.

Details DOI

TCS Journal 2003 Journal Article

Palindrome recognition using a multidimensional tape

  • Therese Biedl
  • Jonathan F. Buss
  • Erik D. Demaine
  • Martin L. Demaine
  • MohammadTaghi Hajiaghayi
  • Tomáš Vinař

The problem of palindrome recognition using a Turing machine with one multidimensional tape is proved to require Θ(n2/log n) time.

Details DOI
v2026.09.13