DSpace at KOASAS
College of Engineering(공과대학)School of Computing(전산학부)CS-Journal Papers(저널논문)

Computing many faces in arrangements of lines and segments

Cited 28 time in webofscience Cited 0 time in scopus
  • Hit : 1017
  • Download : 460
Export
DC FieldValueLanguage
dc.contributor.authorAgarwal, PKko
dc.contributor.authorMatousek, Jko
dc.contributor.authorCheong, Otfriedko
dc.date.accessioned2007-05-25-
dc.date.available2007-05-25-
dc.date.created2012-02-06-
dc.date.created2012-02-06-
dc.date.issued1998-04-
dc.identifier.citationSIAM JOURNAL ON COMPUTING, v.27, no.2, pp.491 - 505-
dc.identifier.issn0097-5397-
dc.identifier.urihttp://hdl.handle.net/10203/323-
dc.description.abstractWe present randomized algorithms for computing many faces in an arrangement of lines or of segments in the plane, which are considerably simpler and slightly faster than the previously known ones. pn The main new idea is a simple randomized O(n log n) expected time algorithm for computing root n cells in an arrangement of n lines.-
dc.description.sponsorshipA part of this work was done while the first and third authors were visiting Charles University and while the first author was visiting Utrecht University. The first author has been supported by National Science Foundation Grant CCR-93-01259 and an NYI aword. The second author has been supported by Charles University grant No. 351 and Czech Republic Grant GACR 201/93/2167. The third author has been supported by the Netherlands' Organization for Scientific Research (NWO) and partially supported by ESPRIT Basic Research Action No. 7141 (project ALCOM 2:Algorithms and Complexity).en
dc.languageEnglish-
dc.language.isoenen
dc.publisherSIAM PUBLICATIONS-
dc.subjectPLANAR PARTITION ALGORITHM-
dc.subjectGEOMETRY-
dc.subjectCONSTRUCTION-
dc.subjectCOMPLEXITY-
dc.subjectNUMBER-
dc.subjectEDGES-
dc.subjectRAY-
dc.titleComputing many faces in arrangements of lines and segments-
dc.typeArticle-
dc.identifier.wosid000072436600009-
dc.identifier.scopusid2-s2.0-0001457529-
dc.type.rimsART-
dc.citation.volume27-
dc.citation.issue2-
dc.citation.beginningpage491-
dc.citation.endingpage505-
dc.citation.publicationnameSIAM JOURNAL ON COMPUTING-
dc.identifier.doi10.1137/S009753979426616X-
dc.embargo.liftdate9999-12-31-
dc.embargo.terms9999-12-31-
dc.contributor.localauthorCheong, Otfried-
dc.contributor.nonIdAuthorAgarwal, PK-
dc.contributor.nonIdAuthorMatousek, J-
dc.type.journalArticleArticle-
dc.subject.keywordAuthorarrangements-
dc.subject.keywordAuthorrandom sampling-
dc.subject.keywordAuthorduality-
dc.subject.keywordPlusPLANAR PARTITION ALGORITHM-
dc.subject.keywordPlusGEOMETRY-
dc.subject.keywordPlusCONSTRUCTION-
dc.subject.keywordPlusCOMPLEXITY-
dc.subject.keywordPlusNUMBER-
dc.subject.keywordPlusEDGES-
dc.subject.keywordPlusRAY-
Appears in Collection
CS-Journal Papers(저널논문)
Files in This Item
This item is cited by other documents in WoS
⊙ Detail Information in WoSⓡ Click to see webofscience_button
⊙ Cited 28 items in WoS Click to see citing articles in records_button

Display Simple Item Record

qr_code

  • mendeley

    citeulike

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.


rss_1.0 rss_2.0 atom_1.0