DC Field | Value | Language |
---|---|---|
dc.contributor.author | Aronov, Boris | ko |
dc.contributor.author | Cheong, Otfried | ko |
dc.contributor.author | Dobbins, Michael Gene | ko |
dc.contributor.author | Goaoc, Xavier | ko |
dc.date.accessioned | 2017-03-31T05:40:46Z | - |
dc.date.available | 2017-03-31T05:40:46Z | - |
dc.date.created | 2017-03-20 | - |
dc.date.created | 2017-03-20 | - |
dc.date.created | 2017-03-20 | - |
dc.date.issued | 2017-01 | - |
dc.identifier.citation | DISCRETE & COMPUTATIONAL GEOMETRY, v.57, no.1, pp.104 - 124 | - |
dc.identifier.issn | 0179-5376 | - |
dc.identifier.uri | http://hdl.handle.net/10203/222774 | - |
dc.description.abstract | We show that the union of n translates of a convex body in R-3 can have Theta (n(3)) holes in the worst case, where a hole in a set X is a connected component of R-3 \ X. This refutes a 20-year-old conjecture. As a consequence, we also obtain improved lower bounds on the complexity of motion planning problems and of Voronoi diagrams with convex distance functions. | - |
dc.language | English | - |
dc.publisher | SPRINGER | - |
dc.subject | VORONOI DIAGRAMS | - |
dc.subject | COMPLEXITY | - |
dc.title | The Number of Holes in the Union of Translates of a Convex Set in Three Dimensions | - |
dc.type | Article | - |
dc.identifier.wosid | 000393700500005 | - |
dc.identifier.scopusid | 2-s2.0-84988353079 | - |
dc.type.rims | ART | - |
dc.citation.volume | 57 | - |
dc.citation.issue | 1 | - |
dc.citation.beginningpage | 104 | - |
dc.citation.endingpage | 124 | - |
dc.citation.publicationname | DISCRETE & COMPUTATIONAL GEOMETRY | - |
dc.identifier.doi | 10.1007/s00454-016-9820-4 | - |
dc.contributor.localauthor | Cheong, Otfried | - |
dc.contributor.nonIdAuthor | Aronov, Boris | - |
dc.contributor.nonIdAuthor | Dobbins, Michael Gene | - |
dc.contributor.nonIdAuthor | Goaoc, Xavier | - |
dc.description.isOpenAccess | N | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Union complexity | - |
dc.subject.keywordAuthor | Convex sets | - |
dc.subject.keywordAuthor | Motion planning | - |
dc.subject.keywordPlus | VORONOI DIAGRAMS | - |
dc.subject.keywordPlus | COMPLEXITY | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.