ZIB

Hits per page

hit 1 - 1 | 1 hit

Select All Export

Electronic Resource

Computing simple circuits from a set of line segments (1990)

Rappaport, David ; Imai, Hiroshi ; Toussaint, Godfried T.

Springer

Discrete & computational geometry 5 (1990), S. 289-304

add to mindlist on the mindlist

Details

ISSN: 1432-0444

Source: Springer Online Journal Archives 1860-2000

Topics: Computer Science , Mathematics

Notes: Abstract We address the problem of connecting line segments to form the boundary of a simple polygon—a simple circuit. However, not every set of segments can be so connected. We present anO(n logn)-time algorithm to determine whether a set of segments, constrained so that each segment has at least one endpoint on the boundary of the convex hull of the segments, admits a simple circuit. Furthermore, this technique can also be used to compute a simple circuit of minimum perimeter, or a simple circuit that bounds the minimum area, with no increase in computational complexity.

Type of Medium: Electronic Resource

URL: http://dx.doi.org/10.1007/BF02187791

Library	Location	Call Number	Volume/Issue/Year	Availability

Others were also interested in ...

Paper (German National Licenses)

Fulltext

hit 1 - 1 | 1 hit