Publikation:

Minimum Polygons for Fixed Visibility VC-Dimension

Vorschaubild

Dateien

Zu diesem Dokument gibt es keine Dateien.

Datum

2018

Autor:innen

Herausgeber:innen

Kontakt

ISSN der Zeitschrift

Electronic ISSN

ISBN

Bibliografische Daten

Verlag

Schriftenreihe

Auflagebezeichnung

URI (zitierfähiger Link)
DOI (zitierfähiger Link)
https://doi.org/10.1007/978-3-319-94667-2_6
ArXiv-ID

Internationale Patentnummer

Angaben zur Forschungsförderung

Projekt

Open Access-Veröffentlichung

Sammlungen

Informatik und Informationswissenschaft: Publikationen
Core Facility der Universität Konstanz

Gesperrt bis

Titel in einer weiteren Sprache

Publikationstyp
Beitrag zu einem Konferenzband
Publikationsstatus
Published

Erschienen in

ILIOPOULOS, Costats, ed. and others. Combinatorial Algorithms : 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings. Cham: Springer, 2018, pp. 65-77. Lecture Notes in Computer Science. 10979. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-94666-5. Available under: doi: 10.1007/978-3-319-94667-2_6

Zusammenfassung

Motivated by the art gallery problem, the visibility VC-dimension was investigated as a measure for the complexity of polygons in previous work. It was shown that simple polygons exhibit a visibility VC-dimension of at most 6. Hence there are 7 classes of simple polygons w.r.t. their visibility VC-dimension. The polygons in class 0 are exactly the convex polygons. In this paper, we strive for a more profound understanding of polygons in the other classes. First of all, we seek to find minimum polygons for each class, that is, polygons with a minimum number of vertices for each fixed visibility VC-dimension d. Furthermore, we show that for d<4 the respective minimum polygons exhibit only few different visibility structures, which can be represented by so called visibility strings. On the practical side, we describe an algorithm that computes the visibility VC-dimension of a given polygon efficiently. We use this tool to analyze the distribution of the visibility VC-dimension in different kinds of randomly generated polygons.

Zusammenfassung in einer weiteren Sprache

Fachgebiet (DDC)
004 Informatik

Schlagwörter

Konferenz

29th International Workshop, IWOCA 2018, 16. Juli 2018 - 19. Juli 2018, Singapore
Rezension
undefined / . - undefined, undefined

Forschungsvorhaben

Organisationseinheiten

Zeitschriftenheft

Verknüpfte Datensätze

Zitieren

ISO 690BECK, Moritz, Sabine STORANDT, 2018. Minimum Polygons for Fixed Visibility VC-Dimension. 29th International Workshop, IWOCA 2018. Singapore, 16. Juli 2018 - 19. Juli 2018. In: ILIOPOULOS, Costats, ed. and others. Combinatorial Algorithms : 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings. Cham: Springer, 2018, pp. 65-77. Lecture Notes in Computer Science. 10979. ISSN 0302-9743. eISSN 1611-3349. ISBN 978-3-319-94666-5. Available under: doi: 10.1007/978-3-319-94667-2_6
BibTex
@inproceedings{Beck2018Minim-43345,
  year={2018},
  doi={10.1007/978-3-319-94667-2_6},
  title={Minimum Polygons for Fixed Visibility VC-Dimension},
  number={10979},
  isbn={978-3-319-94666-5},
  issn={0302-9743},
  publisher={Springer},
  address={Cham},
  series={Lecture Notes in Computer Science},
  booktitle={Combinatorial Algorithms : 29th International Workshop, IWOCA 2018, Singapore, July 16-19, 2018, Proceedings},
  pages={65--77},
  editor={Iliopoulos, Costats},
  author={Beck, Moritz and Storandt, Sabine}
}
RDF
<rdf:RDF
    xmlns:dcterms="http://purl.org/dc/terms/"
    xmlns:dc="http://purl.org/dc/elements/1.1/"
    xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
    xmlns:bibo="http://purl.org/ontology/bibo/"
    xmlns:dspace="http://digital-repositories.org/ontologies/dspace/0.1.0#"
    xmlns:foaf="http://xmlns.com/foaf/0.1/"
    xmlns:void="http://rdfs.org/ns/void#"
    xmlns:xsd="http://www.w3.org/2001/XMLSchema#" > 
  <rdf:Description rdf:about="https://kops.uni-konstanz.de/server/rdf/resource/123456789/43345">
    <dc:creator>Storandt, Sabine</dc:creator>
    <dcterms:available rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-09-20T13:33:27Z</dcterms:available>
    <dc:language>eng</dc:language>
    <dc:contributor>Storandt, Sabine</dc:contributor>
    <dc:date rdf:datatype="http://www.w3.org/2001/XMLSchema#dateTime">2018-09-20T13:33:27Z</dc:date>
    <dcterms:title>Minimum Polygons for Fixed Visibility VC-Dimension</dcterms:title>
    <dc:creator>Beck, Moritz</dc:creator>
    <foaf:homepage rdf:resource="http://localhost:8080/"/>
    <void:sparqlEndpoint rdf:resource="http://localhost/fuseki/dspace/sparql"/>
    <bibo:uri rdf:resource="https://kops.uni-konstanz.de/handle/123456789/43345"/>
    <dcterms:issued>2018</dcterms:issued>
    <dspace:isPartOfCollection rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dc:contributor>Beck, Moritz</dc:contributor>
    <dcterms:isPartOf rdf:resource="https://kops.uni-konstanz.de/server/rdf/resource/123456789/36"/>
    <dcterms:abstract xml:lang="eng">Motivated by the art gallery problem, the visibility VC-dimension was investigated as a measure for the complexity of polygons in previous work. It was shown that simple polygons exhibit a visibility VC-dimension of at most 6. Hence there are 7 classes of simple polygons w.r.t. their visibility VC-dimension. The polygons in class 0 are exactly the convex polygons. In this paper, we strive for a more profound understanding of polygons in the other classes. First of all, we seek to find minimum polygons for each class, that is, polygons with a minimum number of vertices for each fixed visibility VC-dimension d. Furthermore, we show that for d&lt;4 the respective minimum polygons exhibit only few different visibility structures, which can be represented by so called visibility strings. On the practical side, we describe an algorithm that computes the visibility VC-dimension of a given polygon efficiently. We use this tool to analyze the distribution of the visibility VC-dimension in different kinds of randomly generated polygons.</dcterms:abstract>
  </rdf:Description>
</rdf:RDF>

Interner Vermerk

xmlui.Submission.submit.DescribeStep.inputForms.label.kops_note_fromSubmitter

Kontakt
URL der Originalveröffentl.

Prüfdatum der URL

Prüfungsdatum der Dissertation

Finanzierungsart

Kommentar zur Publikation

Allianzlizenz
Corresponding Authors der Uni Konstanz vorhanden
Internationale Co-Autor:innen
Universitätsbibliographie
Ja
Begutachtet
Diese Publikation teilen