Stabbing line segments
Copyright policy )Stabbing line segments
An algorithm for the geometric problem of determining a line (called a stabbing line) which intersects each ofn given line segments in the plane is presented. As a matter of fact, the algorithm computes a description of all stabbing lines. A purely geometric fact is proved which infers that this description requiresO(n) space to be specified. Our algorithm computes it inO(n logn) time which is optimal in the worst case.
- Duke University United States
- University of Illinois at Urbana Champaign United States
- McMaster University Canada
- University of Illinois System United States
- Graz University of Technology Austria
algorithm, Analysis of algorithms and problem complexity, geometric transform, 22, 274-281 (1982), plane-sweep, data structures, Discrete mathematics in relation to computer science, computational geometry, divide-and-conquer, dynamization
algorithm, Analysis of algorithms and problem complexity, geometric transform, 22, 274-281 (1982), plane-sweep, data structures, Discrete mathematics in relation to computer science, computational geometry, divide-and-conquer, dynamization
selected citations These citations are derived from selected sources.This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).63 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 1% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!