---
_id: '4116'
abstract:
- lang: eng
  text: 'A straight line that intersects all members of a set S of objects in the
    real plane is called a transversal of S. Geometric transforms are described that
    reduce transversal problems for various types of objects to convex hull problems
    for points. These reductions lead to efficient algorithms for finding transversals
    which are also described. Applications of the algorithms are found in computer
    graphics: “Reproduce the line displayed by a collection of pixels”, and in statistics:
    “Find the line that minimizes the maximum distance from a collection of (weighted)
    points in the plane”.'
acknowledgement: 'The author gratefully acknowledges the criticism of an anonymous
  referee who discovered a serious flaw in an earlier version of this paper. '
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
citation:
  ama: Edelsbrunner H. Finding Transversals for Sets of Simple Geometric-Figures.
    <i>Theoretical Computer Science</i>. 1985;35(1):55-69. doi:<a href="https://doi.org/10.1016/0304-3975(85)90005-2">10.1016/0304-3975(85)90005-2</a>
  apa: Edelsbrunner, H. (1985). Finding Transversals for Sets of Simple Geometric-Figures.
    <i>Theoretical Computer Science</i>. Elsevier. <a href="https://doi.org/10.1016/0304-3975(85)90005-2">https://doi.org/10.1016/0304-3975(85)90005-2</a>
  chicago: Edelsbrunner, Herbert. “Finding Transversals for Sets of Simple Geometric-Figures.”
    <i>Theoretical Computer Science</i>. Elsevier, 1985. <a href="https://doi.org/10.1016/0304-3975(85)90005-2">https://doi.org/10.1016/0304-3975(85)90005-2</a>.
  ieee: H. Edelsbrunner, “Finding Transversals for Sets of Simple Geometric-Figures,”
    <i>Theoretical Computer Science</i>, vol. 35, no. 1. Elsevier, pp. 55–69, 1985.
  ista: Edelsbrunner H. 1985. Finding Transversals for Sets of Simple Geometric-Figures.
    Theoretical Computer Science. 35(1), 55–69.
  mla: Edelsbrunner, Herbert. “Finding Transversals for Sets of Simple Geometric-Figures.”
    <i>Theoretical Computer Science</i>, vol. 35, no. 1, Elsevier, 1985, pp. 55–69,
    doi:<a href="https://doi.org/10.1016/0304-3975(85)90005-2">10.1016/0304-3975(85)90005-2</a>.
  short: H. Edelsbrunner, Theoretical Computer Science 35 (1985) 55–69.
date_created: 2018-12-11T12:07:02Z
date_published: 1985-01-01T00:00:00Z
date_updated: 2022-01-31T11:09:26Z
day: '01'
doi: 10.1016/0304-3975(85)90005-2
extern: '1'
intvolume: '        35'
issue: '1'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://www.sciencedirect.com/science/article/pii/0304397585900052?via%3Dihub
month: '01'
oa: 1
oa_version: Published Version
page: 55 - 69
publication: Theoretical Computer Science
publication_identifier:
  eissn:
  - 0304-3975
  issn:
  - 0304-3975
publication_status: published
publisher: Elsevier
publist_id: '2008'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Finding Transversals for Sets of Simple Geometric-Figures
type: journal_article
user_id: ea97e931-d5af-11eb-85d4-e6957dddbf17
volume: 35
year: '1985'
...