CUTTINGS AND APPLICATIONS

Cited 27 time in webofscience Cited 0 time in scopus
  • Hit : 1240
  • Download : 599
We prove a general lemma on the existence of (1/r)-cutting of geometric objects in E(d) that satisfy certain properties. We use this lemma to construct (1/r)-cuttings of small size for arrangements of line segments in the plane and arrangements of triangles in 3-space; for line segments in the plane we obtain a cutting of size O(r+Ar-2/n(2)), and for triangles in 3-space our cutting has size O(r(2+e)+Ar-3/n(3)). Here A is the combinatorial complexity of the arrangement. Finally, we use these results to obtain new results for several problems concerning line segments in the plane and triangles in 3-space.
Publisher
WORLD SCIENTIFIC PUBL CO PTE LTD
Issue Date
1995-12
Language
ENG
Article Type
Article
Keywords

PARTITIONING ARRANGEMENTS; COMPUTATIONAL GEOMETRY; EPSILON-NETS; ALGORITHM; LINES; SEGMENTS; QUERIES

Citation

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY APPLICATIONS, v.5, no.4, pp.343 - 355

ISSN
0218-1959
URI
http://hdl.handle.net/10203/8141
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
ijcgaversion.pdf(221.68 kB)Download
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 27 items in WoS Click to see citing articles in records_button

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0