---
_id: '4065'
abstract:
- lang: eng
  text: We prove that given n⩾3 convex, compact, and pairwise disjoint sets in the
    plane, they may be covered with n non-overlapping convex polygons with a total
    of not more than 6n−9 sides, and with not more than 3n−6 distinct slopes. Furthermore,
    we construct sets that require 6n−9 sides and 3n−6 slopes for n⩾3. The upper bound
    on the number of slopes implies a new bound on a recently studied transversal
    problem.
acknowledgement: 'The first author acknowledges the support by Amoco Fnd. Fat. Dev.
  Comput. Sci. l-6-44862. Work on this paper by the second author was supported by
  a Shell Fellowship in Computer Science. The third author as supported by the office
  of Naval Research under grant NOOO14-86K-0416. '
article_processing_charge: No
article_type: original
author:
- first_name: Herbert
  full_name: Edelsbrunner, Herbert
  id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
  last_name: Edelsbrunner
  orcid: 0000-0002-9823-6833
- first_name: Arch
  full_name: Robison, Arch
  last_name: Robison
- first_name: Xiao
  full_name: Shen, Xiao
  last_name: Shen
citation:
  ama: Edelsbrunner H, Robison A, Shen X. Covering convex sets with non-overlapping
    polygons. <i>Discrete Mathematics</i>. 1990;81(2):153-164. doi:<a href="https://doi.org/10.1016/0012-365X(90)90147-A">10.1016/0012-365X(90)90147-A</a>
  apa: Edelsbrunner, H., Robison, A., &#38; Shen, X. (1990). Covering convex sets
    with non-overlapping polygons. <i>Discrete Mathematics</i>. Elsevier. <a href="https://doi.org/10.1016/0012-365X(90)90147-A">https://doi.org/10.1016/0012-365X(90)90147-A</a>
  chicago: Edelsbrunner, Herbert, Arch Robison, and Xiao Shen. “Covering Convex Sets
    with Non-Overlapping Polygons.” <i>Discrete Mathematics</i>. Elsevier, 1990. <a
    href="https://doi.org/10.1016/0012-365X(90)90147-A">https://doi.org/10.1016/0012-365X(90)90147-A</a>.
  ieee: H. Edelsbrunner, A. Robison, and X. Shen, “Covering convex sets with non-overlapping
    polygons,” <i>Discrete Mathematics</i>, vol. 81, no. 2. Elsevier, pp. 153–164,
    1990.
  ista: Edelsbrunner H, Robison A, Shen X. 1990. Covering convex sets with non-overlapping
    polygons. Discrete Mathematics. 81(2), 153–164.
  mla: Edelsbrunner, Herbert, et al. “Covering Convex Sets with Non-Overlapping Polygons.”
    <i>Discrete Mathematics</i>, vol. 81, no. 2, Elsevier, 1990, pp. 153–64, doi:<a
    href="https://doi.org/10.1016/0012-365X(90)90147-A">10.1016/0012-365X(90)90147-A</a>.
  short: H. Edelsbrunner, A. Robison, X. Shen, Discrete Mathematics 81 (1990) 153–164.
date_created: 2018-12-11T12:06:44Z
date_published: 1990-04-15T00:00:00Z
date_updated: 2022-02-22T15:45:55Z
day: '15'
doi: 10.1016/0012-365X(90)90147-A
extern: '1'
intvolume: '        81'
issue: '2'
language:
- iso: eng
main_file_link:
- url: https://www.sciencedirect.com/science/article/pii/0012365X9090147A?via%3Dihub
month: '04'
oa_version: None
page: 153 - 164
publication: Discrete Mathematics
publication_identifier:
  eissn:
  - 1872-681X
  issn:
  - 0012-365X
publication_status: published
publisher: Elsevier
publist_id: '2060'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Covering convex sets with non-overlapping polygons
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 81
year: '1990'
...