Covering rectilinear polygons with axis-parallel rectangles

No abstract is available for this paper.

• Publication year

  1999

• Venue

  Symposium on the Theory of Computing

• Publication date

  1999-05-01

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1145/301250.301369
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Close Approximations of Minimum Rectangular Coverings

  1999cited by this paper
• A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP

  1997cited by this paper
• Approximation Algorithms for Covering Polygons with Squares and Similar Problems

  1997cited by this paper
• Close Approximation of Minimum Rectangular Coverings

  1996cited by this paper
• Almost optimal set covers in finite VC-dimension

  1995cited by this paper
• On the hardness of approximating minimization problems

  1994cited by this paper
• Covering polygons is hard

  1988cited by this paper
• A New Method of Image Compression using Irreducible Covers of Maximum Rectangles

  1988cited by this paper
• Improved Bounds for Covering General Polygons with Rectangles

  1987cited by this paper
• An Algorithm for Covering Polygons with Rectangles

  1986cited by this paper
• Minimally covering a horizontally convex orthogonal polygon

  1986cited by this paper
• A fast heuristic for covering polygons by rectangles

  1985cited by this paper
• An algorithm for constructing regions with rectangles: Independence and minimum generating sets for collections of intervals

  1984cited by this paper
• Algorithms for covering polygons by rectangles

  1982cited by this paper
• Covering Regions by Rectangles

  1981cited by this paper
• On the ratio of optimal integral and fractional covers

  1975cited by this paper
• Approximation algorithms for combinatorial problems

  1973cited by this paper
• PERFORMANCE GUARANTEES ON A SWEEP-LINE HEURISTIC FOR COVERING RECTILINEAR POLYGONS WITH RECTANGLES *

  year unknowncited by this paper

• ScrapReCover: An Interactive Optimization System for Freeform Patchwork Layouts

  2025cites this paper
• Efficient Exact Algorithms for Minimum Covering of Orthogonal Polygons with Squares

  2024cites this paper
• Covering Simple Orthogonal Polygons with Rectangles

  2024cites this paper
• Covering Rectilinear Polygons with Area-Weighted Rectangles

  2023influential citation
• A Scheduling Method of Using Multiple SAR Satellites to Observe a Large Area

  2023cites this paper
• Bachelorarbeit Covering Rectilinear Polygons with Few and Small Axis-Aligned Rectangles

  2023cites this paper
• A hybrid heuristic for the rectilinear picture compression problem

  2022cites this paper
• Covering geometric domains

  2021cites this paper
• Orientational variable-length strip covering problem: A branch-and-price-based algorithm

  2021cites this paper
• The maximum 2D subarray polytope: Facet-inducing inequalities and polyhedral computations

  2021cites this paper
• Generating Stable Building Block Structures From Sketches

  2021cites this paper
• Compact geometric representation of qualitative directional knowledge

  2020cites this paper
• FPC: A new approach to firewall policies compression

  2019cites this paper
• Domain Ordering and Box Cover Problems for Beyond Worst-Case Join Processing

  2019cites this paper
• The 2D Subarray Polytope

  2019cites this paper
• Effective and Efficient Summarization of Two-Dimensional Point Data: Approaches for Resource Description and Selection in Spatial Application Scenarios

  2019cites this paper
• Box Covers and Domain Orderings for Beyond Worst-Case Join Processing

  2019cites this paper
• Generation and Analysis of Content for Physics-Based Video Games

  2019influential citation
• Computing Coverage Kernels Under Restricted Settings

  2018cites this paper
• Multi-covering problems and their variants

  2017cites this paper
• On the covering of a polygonal region with fixed size rectangles with an application towards aerial inspection

  2017cites this paper
• Covering Polygons with Rectangles

  2017cites this paper
• Effective model-based mask fracturing for mask cost reduction

  2015cites this paper
• VLSI Routing for Advanced Technology

  2015cites this paper
• Tool-assisted Spreadsheet Refactoring and Parsing Spreadsheet Formulas

  2015cites this paper
• A difference resolution approach to compressing Access Control Lists

  2013cites this paper
• A Complete Bibliography of The Bell System Technical Journal , 1960 – 1969

  2013cites this paper
• Containment of a pair of rotating objects within a container of minimal area or perimeter

  2012cites this paper
• Model-based high-dimensional pose estimation with application to hand tracking

  2012cites this paper
• Hitting sets online and unique-max coloring

  2012cites this paper
• Hitting Sets Online and Vertex Ranking

  2011cites this paper
• On Parsimonious Explanations for 2-D Tree- and Linearly-Ordered Data

  2011cites this paper
• Covering Problems via Structural Approaches

  2011cites this paper
• Sleeved co-clustering of lagged data

  2011cites this paper
• FAST: Fast Adaptive Silhouette Area based Template Matching

  2010cites this paper
• Optimizing Query Processing in Cache-Aware Wireless Sensor Networks

  2010cites this paper
• Parsimonious rule generation for a nature-inspired approach to self-assembly

  2010cites this paper
• Weighted geometric set cover via quasi-uniform sampling

  2010cites this paper
• Silhouette Area Based Similarity Measure for Template Matching in Constant Time

  2010cites this paper
• EQOWSN: Evolutionary-based query optimization over self-organized wireless sensor networks

  2009cites this paper
• Epsilon Nets and Union Complexity

  2009cites this paper
• Integer Linear Programming Models for the Problem of Covering a Polygonal Region by Rectangles

  2009cites this paper
• Epsilon nets and union complexity

  2009cites this paper
• Fast exact and heuristic methods for role minimization problems

  2008cites this paper
• 九州大学学術情報リポジトリKyushu University Institutional Repository Drawing Borders Efficiently

  2008cites this paper
• A partition-based heuristic for translational box covering

  2008cites this paper
• Drawing Borders Efficiently

  2007cites this paper
• Adapting Swarm Intelligence for the Self-Assembly of Prespecified Artificial Structures

  2007influential citation
• ROUGH DRAFT of Full Paper Compressing Rectilinear Pictures and Minimizing Access Control Lists

  2007cites this paper
• A Distributed Energy Efficient Query Processing in Self-Organized Wireless Sensor Networks

  2007cites this paper
• An energy efficient and self-healing 3-dimensional sensor cover

  2007cites this paper
• Compressing rectilinear pictures and minimizing access control lists

  2007cites this paper
• Coverage Strategies in Wireless Sensor Networks

  2006cites this paper
• Connected sensor cover: self-organization of sensor networks for efficient query execution

  2006cites this paper
• Minimum boundary touching tilings of polyominoes

  2006cites this paper
• Turning Clusters into Patterns: Rectangle-Based Discriminative Data Description

  2006cites this paper
• Hyper-rectangle-based discriminative data generalization and applications in data mining

  2006cites this paper
• Optimal 3-dimensional sensor deployment strategy

  2006influential citation
• Improved Approximation Algorithms for Geometric Set Cover

  2005cites this paper
• Rectangle covers revisited computationally

  2005cites this paper
• The Summarization of Hierarchical Data with Exceptions

  2004cites this paper
• Concise descriptions of subsets of structured sets

  2003influential citation
• Concise descriptions of subsets of structured sets

  2003cites this paper
• Approximation schemes for NP-hard geometric optimization problems: a survey

  2003cites this paper
• Connected sensor cover: self-organization of sensor networks for efficient query execution

  2003cites this paper
• about the Internet and Networking : 2010 – 2019

  2003cites this paper
• An Approximation Algorithm for Minimum Convex Cover with Logarithmic Performance Guarantee

  2001cites this paper
• Geometric Decompositions and Networks - Approximation Bounds and Algorithms

  2000cites this paper
• Hardness of Set Cover with Intersection 1

  2000cites this paper
• (In-)Approximability of visibility problems on polygons and terrains

  2000cites this paper